The Law of the Jungle

Sanggeun is the chief of the Sanggeun tribe on the reality show "The Law of the Jungle." This time the destination is the Amazon, where they meet the Heewon tribe, who live high up in the trees. Those trees are connected to one another by rope bridges.

Because an outsider has visited the village for the first time since it was founded, the Heewon chief, after long deliberation, works up the courage to give the visitors a chance to cross the bridges his people built.

Each bridge has a limit on how many people may cross it at the same time. If more people than that cross at once, the Heewon tribe will be greatly startled.

"We must never startle them."

Sanggeun wants to cross the bridges as quickly as possible without startling the Heewon tribe. To do so, he sets the following two rules.

Rule 1. One group at a time!

When two or more people can cross a bridge, they form a single group and cross together. To keep the bridge from collapsing, they stay as close together as possible and match their steps. Even if the bridge would not collapse, two groups may never cross the same bridge at the same time, because several groups crossing at once makes the bridge sway and startles the Heewon tribe. A group may consist of just one person.

Rule 2. Keep moving!

If there is a bridge that no one is crossing, the largest possible group of the people waiting in front of that bridge immediately starts to cross it. This is not the fastest strategy, but if people just wait without crossing, the Heewon tribe might think something is wrong with the bridge and become startled.

Given the information about the bridges and the number of people, write a program that finds the fastest time for everyone to cross all the bridges while obeying the two rules above. Everyone starts in front of the first bridge and must cross all the bridges one by one in the given order.

For example, consider 9 people crossing 2 bridges. The first bridge can be crossed by 3 people at a time in 10 seconds, and the second by 4 people at a time in 60 seconds. Writing the state as (people waiting before the first bridge, people waiting before the second bridge, people who have crossed all bridges), it proceeds as follows.

• Start: (9, 0, 0)
• After 10 s: (6, 3, 0)
• After 20 s: (3, 3, /3:50/, 0) — /3:50/ means a group of 3 is crossing the second bridge with 50 seconds remaining.
• After 30 s: (0, 6, /3:40/, 0)
• After 70 s: (0, 6, 3)
• After 130 s: (0, 2, 7)
• After 190 s: (0, 0, 9)

Thus the fastest time for everyone to cross is 190 seconds.

The input consists of several test cases. The first line of each test case contains two integers $-B$ and $P$, where $B$ is the number of bridges and $P$ is the number of people; neither value exceeds 20. (The first value is given as the negative number $-B$ only to make the data easier to delimit.)

The next $B$ lines each describe one bridge, one per line, in the order they must be crossed. Each line contains two positive integers $C$ and $T$: $C$ is the maximum number of people who may cross that bridge at once, and $T$ is the time it takes to cross it. $C$ is at most 5 and $T$ is at most 100. A single group of up to $C$ people takes exactly $T$ time to cross, regardless of the group's size.

The last line of the input is $0$ $0$ and is not processed.

For each test case, print on its own line the fastest time for everyone to cross all the bridges while obeying the two rules.