94. 大胃王Snorlax

大胃王Snorlax

題目敘述

今天是竹子大學的校慶，有很多神秘的攤販會來擺攤販售平常無法取得的食物。然而你與$Snorlax$比賽看誰$AC$的題目多時，不幸的你輸了，你必須要請他到竹子大學吃飽一餐。

現在竹子大學裡面有$N$個攤販依序由1開始編號到N，每一個攤販只販賣一種食物，食物重量為$W_i$，售價為$C_i$元。由於這些攤販很神祕，你可以向他們購買無限多份的餐點，都不會缺貨。

看起來你今天要虧大了，不過好消息是你知道$Snorlax$一餐最多只能吃下總計為$S$的食物，不會超過。請問你的錢包至少要攜帶幾元，才能確保能支付$Snorlax$一餐的餐費呢?

輸入說明

有多筆測資，但是不超過$200$筆。測資的第一行有一個數字$S$，表示$Snorlax$的食量，第二航有一個數字$N$，表示有幾間攤販，接下來下一行有$N$組數字，每組數字包含兩個數$W_i,C_i$，表示第$i$的攤販每份食物的重量與售價。

保證：

• $1\leq S \leq 100000$
• $1\leq N \leq 100$
• $1 \leq W_i \leq S$
• $1 \leq C_i \leq 100000$

輸出說明

針對每組測資輸出一行，為至少要攜帶多少錢。

範例輸入

5
2
3 3 2 7

範例輸出

14

Judge Setting

run-time limit: 1000 ms
memory limit: 655350 byte
測資數量: 0