D - ネタだけ食べたい寿司 Editorial

Time Limit: 2.525 sec / Memory Limit: 246 MB

配点 : 600600

問題文

寿司が大好きなタカシくんは、回転寿司チェーン店のニコニコ寿司にやってきました。 タカシくんは寿司を食べることで幸福度を得ることができます。 しかし、タカシくんは現在糖質制限中で、普通に食べるよりもシャリを残してネタだけ食べる方が得られる幸福度が高くなります。

タカシくんが席に着くと、NN 皿の寿司が順番に流れてきて、そのうちな好きな寿司を何皿でも取ることができます。 ただし、流れてくる順番でしか寿司を取ることができず、取った寿司を食べ終わってからしか次の寿司を取ることができません。 ここで、寿司を食べ終わるとは、寿司を普通に食べ終わるか、シャリを残してネタだけ食べ終わることを指します。 i(1iN)i (1≦i≦N) 番目に流れてきた寿司を、シャリを残してネタだけを食べた場合は幸福度を XiX_i 得ることができ、普通に食べた場合は幸福度を YiY_i 得ることができます。

テーブルには、横に並べたときに MM 皿まで置ける広さのスペースがあり、タカシくんは寿司を食べ終わるたびにここに皿を置いていきます。 すでに置いてある皿の上には別の皿を何枚でも重ねることができます。 しかし、ネタだけ食べた皿にはシャリが残っているため、その上に別の皿を重ねることはできません。 また、すでに置いてある皿の下に皿を置くことはできません。 皿を置ける場所がなくなった時点で、それ以上寿司を食べることはできません。

タカシくんが得ることのできる幸福度の合計の最大値を答えてください。

制約

  • 1N1051≦N≦10^5
  • 1M1051≦M≦10^5
  • 1Yi<Xi1,0001≦Y_i \lt X_i≦1,000

入力

入力は以下の形式で標準入力から与えられる。

NN MM
X1X_1 Y1Y_1
X2X_2 Y2Y_2
::
XNX_N YNY_N

出力

タカシくんが得られる幸福度の合計の最大値を 11 行で出力してください。最後に改行を出力すること。


入力例 1Copy

Copy
4 1
5 2
5 3
100 50
5 1

出力例 1Copy

Copy
105

1,21,2 番目の寿司を普通に食べ、33 番目の寿司のネタだけを食べると得られる幸福度が 105105 となり、これが最大です。 このとき、44 番目の寿司のように取らない寿司があっても構わないことに注意して下さい。


入力例 2Copy

Copy
5 2
5 2
100 50
5 3
5 1
100 3

出力例 2Copy

Copy
206

入力例 3Copy

Copy
4 5
280 101
456 404
789 707
1000 999

出力例 3Copy

Copy
2525


2025-01-21 (Tue)
12:19:51 +00:00