問題文

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

タカシくんが席に着くと、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

入力例 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