A team of Byteholers has set out on a trip into Bytemountains. Unfortunately they have caused an avalanche and now have to escape it. There is an old cable-bridge over a chasm ahead of them. They have to cross the bridge as quickly as possible. The Byteholers are intimate friends and therefore have decided that either all or none of them shall survive.
The bridge is old and worn-out, so it won't withstand a great weight. The total weight of Byteholers on the bridge at any time cannot exceed some limit. Furthermore it is a cable-bridge, so the Byteholers have to cross it in groups. Next group may enter it only after the previous one has left.
It is known how much time each Byteholer needs to cross the bridge. A crossing time of a group is the crossing time of the slowest member of the group. Total crossing time of all Byteholers is the sum of crossing times of all groups. Obviously it depends on the manner in which they split into groups.
Write a programme that:
There could be multiple inputs.
The first line of the each testcase contains two integers separated by a single space: c - defining the maximal weight allowed for the bridge (100 <= c <= 400) and n - the number of Byteholers (1 <= n <= 16). In each of the following lines there are two integers separated by a single space, describing successive Byteholers: t - the time needed by the Byteholer to cross the bridge (1 <= t <= 50) and w - the weight of the Byteholer (10 <= w <= 100).
Your program should write a single integer for each testcase. The integer should denote the minimal total crossing time of all Byteholers.
100 3 24 60 10 40 18 50 100 3 24 60 10 40 18 50
42 42
Migrated from old NTUJ.
POI 11th
| No. | Testdata Range | Score |
|---|