【題目描述】

馬上又到了一年一度的新年聯(lián)歡，小明作為班里的班長(cháng)，負責組織策劃新年聯(lián)歡活動(dòng)，他決定采購一些獎品獎勵積極參與每個(gè)項目活動(dòng)的同學(xué)。為了激勵更多的人參與活動(dòng)，需要采購的獎品數目越多越好。班費中可支出的錢(qián)數為m??元，現給定商店中n??種可作為獎品的物品的價(jià)格和庫存數量，怎樣才能購得最多的物品數?

【輸入】

輸入一共n＋1??＋1行:

第一行包含兩個(gè)正整數m???(1<m≤100001<??≤10000)和n??(1<n≤1001<??≤100)，表示可支出的費用為m元和可供購買(mǎi)的物品有n??種。

接下來(lái)的n??行，每行包含兩個(gè)數(有一個(gè)空格分隔)，分別表示一種物品的單價(jià)a??和庫存數量b??。a??和b??均不會(huì )超過(guò)10001000。

【輸出】

一個(gè)整數，表示最多可以購買(mǎi)的物品數量。

【輸入樣例】

500 6

100 3

20 15

50 10

35 5

5 6

60 2

【輸出樣例】

25