一群 Byteholers 踏上了前往 Bytemountains 的旅程。不幸的是，他们引发了一场雪崩，现在必须逃离。在他们前方有一座横跨深渊的古老缆桥。他们必须尽快过桥。Byteholers 之间关系亲密，因此他们决定要么所有人一起获救，要么一个都不留。

这座桥年久失修，无法承受过大的重量。任何时候桥上 Byteholers 的总重量都不能超过某个限制。此外，由于这是一座缆桥，Byteholers 必须分组过桥。下一组只有在前一组完全离开后才能上桥。

已知每位 Byteholer 过桥所需的时间。一组人的过桥时间等于该组中过桥最慢成员的时间。所有 Byteholers 的总过桥时间为各组过桥时间之和。显然，这取决于他们如何分组。

请成为他们的救星！计算所有 Byteholers 过桥所需的最短总时间。

编写一个程序：

• 从标准输入读取桥梁和 Byteholers 的描述，
• 确定所有 Byteholers 的最短总过桥时间，
• 将确定的时间写入标准输出。

输入格式

标准输入的第一行包含两个由空格分隔的整数：$w$ - 定义桥梁允许的最大重量 ($100 \le w \le 400$) 和 $n$ - Byteholers 的人数 ($1 \le n \le 16$)。接下来的 $n$ 行中，每行包含两个由空格分隔的整数，描述后续的 Byteholers：$t$ - 该 Byteholer 过桥所需的时间 ($1 \le t \le 50$) 和 $w$ - 该 Byteholer 的重量 ($10 \le w \le 100$)。

输出格式

你的程序应在第一行输出一个整数。该整数表示所有 Byteholers 过桥的最短总时间。

样例

输入 1

100 3
24 60
10 40
18 50

输出 1

42