94. 大胃王Snorlax

0 Judge

Code: 0


大胃王Snorlax

題目敘述

sprout

今天是竹子大學的校慶,有很多神秘的攤販會來擺攤販售平常無法取得的食物。然而你與$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