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\)