電電拿到了一張員生社\(禮卷\)，面額為 \(n\) 元
員生社共有 \(t\) 件商品
員生社的每件商品都有一個價格 \(p_i\) 及重量 \(w_i\)
求\(禮物卷\)可買到的最大總重。

輸入格式

第一行 有一個數 \(n\), \(n ≤ 10^3\)
第二行 有一個數 \(t\), \( t ≤ 10^3\)
接下來有 \(t\) 行
每行有兩個數 \(p_i\), \(w_i\), 皆小於 \(10^6\)

輸出格式

輸出最大重量

範例輸入

50
5
13 17
23 27
10 37
20 14
50 71

範例輸出

81