Passage

A team of Byteholers has set out on a trip into the Bytemountains. Unfortunately they have set off an avalanche and now must escape it. Ahead of them lies an old cable bridge over a chasm, and they must cross it as quickly as possible. The Byteholers are close friends, so they have decided that either all of them survive or none of them do.

The bridge is old and worn out, so it cannot bear too much weight: at any moment the total weight of the Byteholers standing on the bridge must not exceed a given limit. Because it is a cable bridge, the Byteholers must cross in groups — the next group may step onto the bridge only after the previous group has completely left it.

For each Byteholer the time needed to cross the bridge is known. The crossing time of a group equals the crossing time of its slowest member, and the total crossing time is the sum of the crossing times of all groups. This total clearly depends on how the Byteholers are split into groups.

Help them! Write a program that:

• reads the description of the bridge and the Byteholers from standard input,
• determines the minimum total crossing time of all the Byteholers,
• writes that time to standard output.

The first line contains two integers separated by a single space: $W$, the maximum total weight the bridge can bear ($100 \le W \le 400$), and $n$, the number of Byteholers ($1 \le n \le 16$).

Each of the next $n$ lines contains two integers separated by a single space describing one Byteholer: $t$, the time that Byteholer needs to cross the bridge ($1 \le t \le 50$), and $w$, that Byteholer's weight ($10 \le w \le 100$).

Print a single integer: the minimum total crossing time of all the Byteholers.