Description

有一支$n$个人的队伍要过一座限重为$W$的桥，我们规定这支队伍过桥时只能分组过，即当一组全部过去后，下一组才能接着过。给定每个队员的重量$w_i$和过桥时间$t_i$，一组人的过桥时间为花费时间最多的人的时间。问如何分组使得总的过桥时间最短。

Input

• 第一行为两个正整数$W, n$
• 接下来$n$行每行两个数$t_i, w_i$。

Output

• 仅一个数，为最小花费时间。

Sample

Input

100 3
24 60
10 40
18 50

Output

42

Hint

• 对于40%的数据，$n\le 8$
• 对于70%的数据，$n\le 12$
• 对于100%的数据，$n\le 16, 100\le W\le 400, 1\le t\le 50, 10\le w\le 100$