題目描述

超巿老闆為了獎賞最優秀的員工，舉行了超巿限時任取貨品大賽，他對員工說：“各位，我們超巿內有不同的貨品，取每一件都需要一些時間，每一件也有它自身的價值。我會給你一段時間，在這段時間裡，你可以拿取一些貨品。如果你是一個優秀的員工，你應該可以令拿取到的貨品的總價值最大。”

輸入格式

請考慮多組輸入，每組輸入的第一行有兩個整數 T（1 <= T <= 1000）和 M（1 <= M <= 100），用一個空格隔開，T 代表總共能夠用來取貨品的總時間， M 代表超巿裡的貨品的數目。接下來的 M 行每行包括兩個在1到100之間（包括1和100）的整數，分別表示取貨的時間和這貨品的價值。

輸出格式

每組輸出只包含一個整數，表示在規定的時間內，可以取到的所有貨品的最大總價值。

Samples

70 3
1 2
69 10
71 100

12

原始資料

• Zero1 題號：a332
• Hydro 題號：Z0332
• Locale：zh_TW
• Display：open