[SXOI2016]过桥

[SXOI2016]过桥

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

信息

难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者