蒜头君酷爱搭积木，他用积木搭了 $n$ 辆重量为 $w_i$的小车和一艘最大载重量为 $W$ 的小船，他想用这艘小船将 $n$ 辆小车运输过河。

每次小船运载的小车重量不能超过 $W$。另外，小船在运载小车时，每辆小车会对小船有一个损坏值 $s_i$，当多辆小车一起运载时，该趟运载对小船的损坏值为船上所有小车的最大损坏值。

现在蒜头君想知道，如何用小船运载 $n$ 辆小车，可以使得对小船造成的总损坏值最小。

输入格式

第一行输入两个数 $W$ 和 $n$（$100 \leq w \leq 400，1 \leq n \leq 16$），分别表示小船的最大载重量和小车总数。

接下来输入 $n$ 行，每行输入两个整数 $s_i$和 $w_i$（$1 \leq s_i \leq 50，10 \leq w_i \leq 100$），分别表示每辆小车对小船的损坏值和每辆小车的重量。

输出格式

输出一行，输出一个整数，表示用小船运载 $n$ 辆小车，最小的总损坏值。

样例

样例输入

90 4
32 50
15 20
40 50
13 40

样例输出

72

数据范围与提示

• 对于$50\\%$的数据，$1 \leq n \leq 12$
• 对于$100\\%$的数据，$1 \leq n \leq 16$

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$131022\mathrm{KB}$