该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

附加文件

【题目描述】

在漆黑的夜里，N 位旅行者来到了一条河边，他们要过河。幸运的是，他们发现了一座桥。不幸的是，这座桥已经破旧不堪，承重有限。如果各自单独过桥的话，每个人所需要的时间已知；而如果多人同时过桥，所需要的时间就是走得最慢的那个人单独过桥所需的时间。问题是，如何设计一个方案，让这 N 个人尽快过桥。

注意：任一时刻，桥上所有人的重量不能超过桥的载重量。前一批过桥的人下桥后，下一批人可以立即上桥，中间不耽误时间。

【输入格式】

第一行是两个整数 M、N，表示桥的载重量为 M，共有 N 个人要过河

接下来 N 行，每行两个整数 Ti、Wi，表示第 i 个人单独过桥所需要时间为 Ti，他的重量为 Wi。

【输出格式】

输出所有人都过完桥需要用的最少时间。

【样例输入】

120 3
33 85
20 30
22 66

【样例输出】

55

【数据范围】

$40\%$ 的数据，$1 ≤ N ≤ 5$

$100\%$ 的数据，$1 ≤ N ≤ 16$，$100 ≤ M ≤ 400$，$1 ≤ Ti ≤50$，$10 ≤ Wi ≤ 100$。