P5911 [POI 2004] PRZ

A team encountered an avalanche while climbing. While escaping, they came across a bridge and need to cross it as quickly as possible.

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.

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 one integer, the minimum total time needed to cross the bridge.

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