005 - カップ麺うめぇ！うますぎるっ！ズルルルルル！

時間制限 1 秒 / メモリ制限 32 MB / 得点 35 / x 13 /

TLE
1sec
MLE
32MB
得点
35

問題うめぇ！うますぎるっ！星3つ！あああああああああ！

赤いきつねのどん兵衛と契約して何でも見える力を得た一平ちゃんは、あるカップ麺職人の工場を見てびっくり仰天。
麺職人の弟子のマルちゃんがUFOに乗りながら実はカップ麺を作っていたのです！
このことを知った一平ちゃんは自分もマルちゃんにカップ麺を作らせようと思いました。
しかし、マルちゃんには仕事の流儀がありました。
エネルギー源であるチェケェンリャーメンをマルちゃんに与えないと、丸ちゃんは仕事をしません。
また、チェケェンリャーメンを１個与えると、マルちゃんは仕事を１行程進めることがわかりました。
つまり、ある日にチェケェンリャーメンを３個与えるとマルちゃんはその日に仕事を３行程進めます。
そのことを知った一平ちゃんは早速仕事を依頼しようとしますが、とんでもないことになります。
チェケェンリャーメンを作っている会社が不景気のせいで、チェケェンリャーメンの値段が日によって高くなったり安くなったりしてしまうのです。
チェケェンリャーメンを１つも持っていない一平ちゃんは出来る限りやすい日にまとめ買いをしておこうと思いました。
ですが、もう１つ大変なことに気づきます。
チェケェンリャーメンは買ったその日に食べないと、BaGooooN!!と爆発して、食べられなくなってしまうそうです。
お小遣い制で生きている一平ちゃんは期日内の各日においてチェケェンリャーメンを買うために使える金額の一覧とチェケェンリャーメンが期日内の各日で１個何円するのかの一覧を作り、私に、期日内に終わるように、そして、出来る限りかかる予算を安くするようなチェケェンリャーメンの買い方をした場合の消費するお金を求めるプログラムを書いてほしいと私に依頼してきました。 一番最初に解いた人には一平ちゃんからカップ麺１年分が贈呈されるそうなので、がんばりましょう。 ※この問題に出てきた名前と、カップ麺の商品名は一切関係がありません。

入力

n k
m1 c1
m2 c2
m3 c3
.
.
.
mn cn

１行目には、一平ちゃんがカップ麺を作る期日nとカップ麺を作る行程の数kが与えられる。つまり、n日以内に全k行程を終えなくてはならない。
2行目からは、一平ちゃんがi日目にチェケェンリャーメンを買うことに使える予算miと、i日目のチェケェンリャーメンの１個の値段ciが与えられる。この予算は残っても明日へ繰り越すことは出来ない。

出力

仕事が期日内に終わり、最もお金を消費しないチェケェンリャーメンの買い方をした場合の消費するお金を出力せよ。もし、どうがんばっても期日内に終わらない場合は"NA"と出力しなさい。

制約

全ての入出力ケースについて以下を満たす。

  • 1 ≦ n ≦ 1000
  • 1 ≦ k ≦ 5000
  • 1 ≦ mi,ci ≦ 10000

入出力例

入力例1

3 5
600 300
400 200
100 100

出力例1

1100

入力例2

5 5
600 250
500 200
100 100
400 800
200 200

出力例2

950

入力例3

1 1000
1 10000

出力例3

NA