← 返回题目列表

AtCoder · abc457_c

C. 长序列

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你整数 N 和 K,以及 N 整数序列 A_1, A_2, \ldots, A_N 和长度-N 整数序列 C = (C_1, C_2, \ldots, C_N)。整数序列的长度 A_i is L_i,和 A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i})。可以保证 \displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i.

构造一个整数序列 B = (B_1, B_2, \ldots, B_{\sum_{i=1}^N C_iL_i}) 来自 A 和 C 使用以下过程。

  • 让 B 是长度的整数序列 0.
  • 对于 i = 1, 2, \ldots, N 按此顺序执行以下操作:
    • 这样做 C_i 次:追加 A_i 到年底 B.

查找值 B_K.

约束

  • 1 \le N
  • 1 \le L_i
  • \displaystyle \sum_{i=1}^N L_i \le 2 \times 10^5
  • 1 \le A_{i,j} \le 10^9 (1 \le j \le L_i)
  • 1 \le C_i \le 10^9
  • \displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
L_1 A_{1,1} A_{1,2} \ldots A_{1,L_1}
L_2 A_{2,1} A_{2,2} \ldots A_{2,L_2}
\vdots
L_N A_{N,1} A_{N,2} \ldots A_{N,L_N}
C_1 C_2 \ldots C_N

输出

输出答案。


示例输入 1

3 9
3 1 3 2
1 3
2 4 3
1 3 2

示例输出 1

4

B 的构造如下:

  • 让 B = ().
  • 追加 A_1 到年底 B 一次。我们得到 B = (1, 3, 2).
  • 追加 A_2 到年底 B 三次。我们得到 B = (1, 3, 2, 3, 3, 3).
  • 追加 A_3 到年底 B 两次。我们得到 B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3).

对于 B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3),我们有 B_9 = 4,所以输出 4.


示例输入 2

3 1
1 7
1 111
1 5
1 100 10000

示例输出 2

7

示例输入 3

3 3163812
5 1 2 3 4 5
4 9 8 7 6
2 10 11
87043 908415 9814

示例输出 3

9