C - Long Sequence 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

整数 N,K と N 個の整数列 A_1,A_2,\ldots,A_N 、長さ N の整数列 C=(C_1,C_2,\ldots,C_N) が与えられます。整数列 A_i の長さは 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 が保証されます。

A と C から以下の手順で整数列 B=(B_1,B_2,\ldots,B_{\sum_{i=1}^N C_iL_i}) を構成します。

  • B を長さ 0 の整数列とする。
  • i=1,2,\ldots,N の順に以下の操作を行う：
    • B の末尾に A_i を連結させる操作を C_i 回行う。

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=() とする。
  • B の末尾に A_1 を連結させる操作を 1 回行う。B=(1,3,2) となる。
  • B の末尾に A_2 を連結させる操作を 3 回行う。B=(1,3,2,3,3,3) となる。
  • B の末尾に A_3 を連結させる操作を 2 回行う。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

Score : 300 points

Problem Statement

You are given integers N and K, along with N integer sequences A_1, A_2, \ldots, A_N and a length-N integer sequence C = (C_1, C_2, \ldots, C_N). The length of integer sequence A_i is L_i, and A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}). It is guaranteed that \displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i.

Construct an integer sequence B = (B_1, B_2, \ldots, B_{\sum_{i=1}^N C_iL_i}) from A and C using the following procedure.

  • Let B be an integer sequence of length 0.
  • For i = 1, 2, \ldots, N in this order, perform the following operation:
    • Do this C_i times: append A_i to the end of B.

Find the value of B_K.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Output the answer.

Sample Input 1

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

Sample Output 1

4

B is constructed as follows:

  • Let B = ().
  • Append A_1 to the end of B once. We get B = (1, 3, 2).
  • Append A_2 to the end of B three times. We get B = (1, 3, 2, 3, 3, 3).
  • Append A_3 to the end of B twice. We get B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3).

For B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3), we have B_9 = 4, so output 4.

Sample Input 2

3 1
1 7
1 111
1 5
1 100 10000

Sample Output 2

7

Sample Input 3

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

Sample Output 3

9