You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一只队伍在爬山时碰到了雪崩，他们在逃跑时遇到了一座桥，他们要尽快的过桥。

题目描述

桥已经很旧了, 所以它不能承受太重的东西。任何时候队伍在桥上的人都不能超过一定的限制。 所以这只队伍过桥时只能分批过，当一组全部过去时，下一组才能接着过。队伍里每个人过桥都需要特定的时间，当一批队员过桥时时间应该算走得最慢的那一个，每个人也有特定的重量，我们想知道如何分批过桥能使总时间最少。

输入格式

第一行两个数: $W$ 表示桥能承受的最大重量和 $n$ 表示队员总数。

接下来 $n$ 行：每行两个数: $t$ 表示该队员过桥所需时间和 $w$ 表示该队员的重量。

输出格式

输出一个数表示最少的过桥时间。

100 3
24 60
10 40
18 50

42

提示

对于 $100\%$ 的数据，$100\le W \le400$ ，$1\le n\le 16$，$1\le t\le50$，$10\le w\le100$。