Problem Description

There are $ N $ sequences, where the $ i $-th sequence is an arithmetic sequence with a length of $ A_i $, a first term of $ B_i $, and a common difference of $ C_i $.
Concatenate all $ N $ sequences into one sequence and output the $ K $-th smallest element.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $\vdots$ $ A_N $ $ B_N $ $ C_N $

Output Format

Output the $ K $-th smallest element of the concatenated sequence.

Sample Input and Output

Sample Input #1

2 4
3 2 2
2 3 4

Sample Output #1

6

Sample Input #2

2 10
4 1000000000 1000000000
6 1000000000 1000000000

Sample Output #2

6000000000

Sample Input #3

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

Sample Output #3

16

Notes/Hints

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$
• $1 \leq K \leq \sum_{i=1}^N A_i$
• All inputs are integers.

Sample Explanation 1

The first sequence is $ (2, 4, 6) $ and the second sequence is $ (3, 7) $. Concatenating these two sequences results in $ (2, 4, 6, 3, 7) $. Therefore, the 4th smallest element is $ 6 $.

Sample Explanation 2

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

见题面 Input 部分

见题面 Output 部分