Problem : 41 - 烤箱

Problem Statistics

Solved Member: 51　　Submission: 122　　User Tried: 54

Statement:

如果你以為我們還要討論時下最流行的微波爐，那你就錯了。

你玩過烤箱Online嗎？這是一款充滿歡樂的遊戲。遊戲是這樣的，你擁有N個道具，每使用一次會消耗你W的魔力，並且得到V的興奮感！當然，一個道具可以使用無數次，這也是這款遊戲大受歡迎的原因。當你的興奮感到達某一程度時，你就可以進烤箱裡一次將興奮感爆發出來。

志明十分希望自己能得到最高興奮感，你能否幫他算出最興奮是多興奮呢?

Input:Output:

第一行有兩個正整數M N，代表的是志明的魔力上限與他擁有的道具數。
第二行到第N+1行各有兩個數字Vi Wi，代表每種道具的興奮感與魔力消耗。
(1 <= M, N, Vi, Wi <= 10000)

請輸出你認為是答案的答案。

Sample Input:Sample Output:

300 4
100 60
250 120
120 100
35 20

605

HINT:

從第二種拿2份，第四種拿3份，250 * 2 + 35 * 3 = 605.

Source:

USACO Training

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	999ms	65536kb
1	999ms	65536kb	8
2	999ms	65536kb	8
3	999ms	65536kb	8
4	999ms	65536kb	8
5	999ms	65536kb	8
6	999ms	65536kb	8
7	999ms	65536kb	8
8	999ms	65536kb	8
9	999ms	65536kb	9
10	999ms	65536kb	9
11	999ms	65536kb	9
12	999ms	65536kb	9