题目描述

$Bob$ 最近对过桥问题很感兴趣，$n$ 个人要过桥，第 $i$ 个人的重量是 $w_i$ , 过桥时间是 $t_i$ 。

现在要对这 $n$ 个人进行分组，分到一个组的人一同过桥，但桥的最大承重是 $W$ ,即一个组的人总重量不能超过 $W$ ，这个组过桥的时间取决于最慢过桥的人，即一个组过桥时间是组内最大的 $t_i$ 。

当一个组的人全部过桥后，才能安排下一组过桥，$Bob$ 想知道如何安排分组，才能让总过桥时间最短，请帮助 $Bob$ 计算最短过桥时间 。

如果无法安排过桥，输出 $-1$

输入格式

第一行两个整数 ，桥的最大承重 $W$ , 过桥人数 $n$ ;

接下来 $n$ 行，每行两个整数，表示第 $i$ 个人过桥时间 $t_i$ 和重量 $w_i$ .

输出格式

一个整数，表示最短过桥时间。

100 3
24 60
10 40
18 50

42

213 5
45 82
66 95
30 213
5 73
79 155

180

300 16
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100
1 100

6

50 3
20 3
50 51
30 2

-1

数据规模与约定

$Subtask1$ : $1\le n \le 10 ,1 \le t_i \le 100, 1 \le w_i \le 300, 1 \le W \le 1000$ , 数据随机 , $30$ 分

$Subtask2$ : $1\le n \le 17 ,1 \le t_i \le 100, 1 \le w_i \le 300, 1 \le W \le 1000$ , 数据随机 , $30$ 分

$Subtask3$ : $1\le n \le 17 ,1 \le t_i \le 100, 1 \le w_i \le 300, 1 \le W \le 1000$ , $40$ 分