Description

The bridge is very old, so it cannot hold things that are too heavy. At any moment, the total weight of the people on the bridge cannot exceed a fixed limit. Therefore, the team can only cross the bridge in several batches. Only after one batch has completely crossed can the next batch start crossing.

Each person needs a specific amount of time to cross the bridge. For one batch, the time taken should be counted as the slowest person's time in that batch. Each person also has a specific weight. You need to determine how to split the team into batches so that the total time is minimized.

Input Format

The first line contains two integers: $W$ (the maximum weight the bridge can bear) and $n$ (the total number of team members).

The next $n$ lines each contain two integers: $t$ (the time needed for this member to cross) and $w$ (this member's weight).

Output Format

Output one integer, the minimum total time needed to cross the bridge.

100 3
24 60
10 40
18 50

42

Hint

For $100\%$ of the testdata, $100 \le W \le 400$, $1 \le n \le 16$, $1 \le t \le 50$, $10 \le w \le 100$.

Translated by ChatGPT 5