G - K番目の要素 解説 /

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

配点 : 6 点

注意

この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

数列が N 個あり、i 番目の数列は長さ A_i, 初項 B_i, 公差 C_i の等差数列です。
N 個の数列を全て連結して 1 つの数列にしたとき、小さい方から K 番目の要素を答えてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 1 \leq C_i \leq 10^9
  • \displaystyle 1 \leq K \leq \sum_{i=1}^N A_i
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 B_1 C_1
\vdots
A_N B_N C_N

出力

連結した数列の小さい方から K 番目の要素を出力せよ。

入力例 1

2 4
3 2 2
2 3 4

出力例 1

6

1 番目の数列は (2, 4, 6) 、2 番目の数列は (3, 7) なので、この二つの数列を連結すると (2, 4, 6, 3, 7) になります。
よって 4 番目に小さい要素は 6 となります。

入力例 2

2 10
4 1000000000 1000000000
6 1000000000 1000000000

出力例 2

6000000000

答えが 32 bit 整数に収まらない可能性があることに注意してください。

入力例 3

5 10
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9

出力例 3

16

Score : 6 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N sequences of numbers. The i-th of them is an arithmetic progression of length A_i with the initial term B_i and the common difference C_i.
If all these N sequences are concatenated into one sequence, what is the K-th smallest element of that sequence?

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 1 \leq C_i \leq 10^9
  • \displaystyle 1 \leq K \leq \sum_{i=1}^N A_i
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 B_1 C_1
\vdots
A_N B_N C_N

Output

Print the K-th smallest element of the sequence after the concatenation.

Sample Input 1

2 4
3 2 2
2 3 4

Sample Output 1

6

The first sequence is (2, 4, 6), and the second sequence is (3, 7), so we have (2, 4, 6, 3, 7) after the concatenation.
Therefore, the fourth smallest element is 6.

Sample Input 2

2 10
4 1000000000 1000000000
6 1000000000 1000000000

Sample Output 2

6000000000

Note that the answer may not fit into a 32-bit integer.

Sample Input 3

5 10
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9

Sample Output 3

16