← 返回题目列表

AtCoder · dwango2017qual_d

D. 只想吃的寿司

中文机器翻译题面 查看原题

配点 : 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