AT_past202109_g K番目の要素

[problemUrl]: https://atcoder.jp/contests/past202109-open/tasks/past202109_g 数列が $ N $ 個あり、$ i $ 番目の数列は長さ $ A_i $, 初項 $ B_i $, 公差 $ C_i $ の等差数列です。 $ N $ 個の数列を全て連結して $ 1 $ つの数列にしたとき、小さい方から $ K $ 番目の要素を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_N $ $ B_N $ $ C_N $

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

### 注意 この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ - 入力は全て整数である。 ### Sample Explanation 1 $ 1 $ 番目の数列は $ (2,\ 4,\ 6) $ 、$ 2 $ 番目の数列は $ (3,\ 7) $ なので、この二つの数列を連結すると $ (2,\ 4,\ 6,\ 3,\ 7) $ になります。 よって $ 4 $ 番目に小さい要素は $ 6 $ となります。 ### Sample Explanation 2 答えが $ 32 $ bit 整数に収まらない可能性があることに注意してください。