题目描述

你是一名星际探险家，正准备前往一个陌生星球执行采集任务。
你的飞船货舱容量有限，最多只能携带 T 千克 的物资回地球（1 ≤ T ≤ 1000）。
星球表面有 M 种 稀有矿石（1 ≤ M ≤ 100），每种矿石你最多只能采集 一块。

每种矿石有两个属性：

• 重量 wᵢ（千克）（1 ≤ wᵢ ≤ 100）
• 价值 vᵢ（星际币）（1 ≤ vᵢ ≤ 100）

你的目标是，在不超过货舱最大载重的前提下，让带回地球的矿石总价值最大。

输入格式

第一行有两个整数 T 和 M，用一个空格隔开，T 代表货舱的最大载重（千克），M 代表矿石的种类数。
接下来的 M 行，每行包含两个整数 wᵢ 和 vᵢ，分别表示第 i 种矿石的重量与价值。

输出格式

一行，包含一个整数，表示在规定载重内可以带回的矿石最大总价值。

样例

输入样例

100 5
10 20
30 65
25 50
40 80
50 90

输出样例

155

提示

• 对于 30% 的数据，M ≤ 10；
• 对于全部数据，M ≤ 100。