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$。