配点 : 600 点
問題文
热爱寿司的Takashi来到了回转寿司连锁店Niconico Sushi。 隆君可以通过吃寿司获得幸福。 不过,隆君目前正在限制碳水化合物的摄入量,如果他不吃寿司米饭,只吃配料而不是正常吃东西,他会更开心。
当Takashi君就座时,N 寿司会按顺序送到您面前,您可以随意挑选寿司。 不过,你只能按照上来的顺序拿走寿司,而且只有吃完你拿的那个寿司后才能拿下一个寿司。 这里,吃完寿司是指正常吃完寿司,或者只吃完配料而将寿司放在一边。 i (1≦i≦N) 如果你只吃配料而留下寿司饭,你的幸福感会增加。 X_i 如果你正常饮食,你的幸福感就会增加。 可以获得 Y_i 。
该表有 M 这里有足够大的空间可以放盘子,隆君每次吃完寿司都会把盘子放在这里。 您可以在已放置的盘子顶部堆叠任意数量的盘子。 不过,因为盘子里还剩下米饭,只能吃配料,所以不能再放盘子。 另外,您不能将盘子放置在已放置的盘子下面。 一旦你没有足够的空间来放置你的盘子,你就不能再吃寿司了。
请回答隆君可以获得的最高总幸福度。
制約
- 1≦N≦10^5
- 1≦M≦10^5
- 1≦Y_i \lt X_i≦1,000
入力
输入是按以下格式从标准输入给出的。
N M X_1 Y_1 X_2 Y_2 : X_N Y_N
出力
Takashi君可以获得的最大总幸福感。 1 行。在末尾输出换行符。 正常吃第
入力例 1
4 1 5 2 5 3 100 50 5 1
出力例 1
105
1,2 个寿司,3 只吃寿司配料获得的幸福 105 ,这是最大值。 这时, 请注意,可能有一些寿司您不吃,例如第4 个寿司。
入力例 2
5 2 5 2 100 50 5 3 5 1 100 3
出力例 2
206
入力例 3
4 5 280 101 456 404 789 707 1000 999
出力例 3
2525