分数: 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