インフルエンサーへの道
数か月にわたってソーシャルメディアに多くのコンテンツを投稿してきました。そこで、最も人気のあった時期を分析したいと考えています。そのために、長さが
t を超えない期間のうちで、あなたのコンテンツが獲得したビュー数の合計が最大となる値を知りたいのです。入力
最初の行には、二つの整数
n (1 ≤ n ≤ 10^5) と t (1 ≤ t ≤ 10^9) が与えられます。ここで n は投稿したコンテンツの数、t は検討したい最大の時間区間を表します。続く
n 行には、スペース区切りの整数 t_i, v_i が含まれており、それぞれ投稿された時刻と、その投稿によって得られたビュー数を示します (1 ≤ t_i, v_i ≤ 10^9)。出力
長さが
t を超えない時間区間のなかで得られるビュー数の合計値の最大値を出力してください。Examples
Input | Output |
4 5
10 1000
12 1500
6 2000
1 1100 | 3100 |
Explanation
最後の2つの投稿（時刻 1 と 6 の投稿）を取り上げると、ビュー数が 2000 + 1100 となり合計 3100 になります。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB