정글의 법칙

상근이는 예능 프로그램 "정글의 법칙"에 출연하는 상근족의 족장이다. 이번 목적지는 아마존이며, 그곳에서 나무 위에 사는 희원 부족을 만났다. 희원 부족이 사는 나무들은 줄로 만든 다리로 서로 연결되어 있다.

마을이 생긴 이래 처음으로 외부인이 찾아왔기에, 희원 부족의 족장은 오랜 고민 끝에 용기를 내어 자신들이 만든 다리를 건너 볼 기회를 주기로 했다.

각 다리는 동시에 건널 수 있는 사람 수가 정해져 있다. 이보다 많은 사람이 한꺼번에 지나가면 희원 부족은 크게 놀란다.

"절대 이분들을 놀라게 하면 안 돼."

상근이는 희원 부족을 놀라게 하지 않으면서 다리를 최대한 빨리 건너려 한다. 이를 위해 상근이는 다음 두 가지 규칙을 정했다.

규칙 1. 한 번에 한 그룹만!

한 다리를 두 명 이상이 건널 수 있을 때, 그 사람들은 한 그룹을 이루어 동시에 건넌다. 이때 다리가 무너지지 않도록 서로 최대한 붙어 걸음을 맞추어 걷는다. 다리가 무너지지 않더라도 두 그룹이 같은 다리를 동시에 건널 수는 없다. 여러 그룹이 함께 건너면 다리가 흔들려 희원 부족이 놀라기 때문이다. 그룹은 한 명으로 이루어질 수도 있다.

규칙 2. 쉬지 말고 계속 움직여라!

건너는 사람이 아무도 없는 빈 다리가 있다면, 그 다리 앞에서 기다리는 사람들 중 최대 인원이 곧바로 한 그룹을 이루어 건너기 시작한다. 이 방법이 가장 빠른 것은 아니지만, 사람들이 다리를 건너지 않고 기다리기만 하면 희원 부족은 다리에 문제가 생겼다고 오해하여 놀랄 수 있기 때문이다.

다리의 정보와 사람 수가 주어졌을 때, 위 두 규칙을 지키면서 모든 사람이 모든 다리를 건너는 데 걸리는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 사람들은 첫 번째 다리 앞에서 출발하여 주어진 순서대로 모든 다리를 차례로 건너야 한다.

예를 들어 9명이 다리 2개를 건너는 경우를 생각해 보자. 첫 번째 다리는 한 번에 3명이 10초 만에, 두 번째 다리는 한 번에 4명이 60초 만에 건널 수 있다. 상태를 (첫 번째 다리 앞 대기 인원, 두 번째 다리 앞 대기 인원, 모든 다리를 건넌 인원)으로 나타내면 다음과 같이 진행된다.

시작: (9, 0, 0)
10초 후: (6, 3, 0)
20초 후: (3, 3, /3:50/, 0) — /3:50/은 3명 그룹이 두 번째 다리를 건너는 중이며 50초가 남았다는 뜻이다.
30초 후: (0, 6, /3:40/, 0)
70초 후: (0, 6, 3)
130초 후: (0, 2, 7)
190초 후: (0, 0, 9)

따라서 모든 사람이 다리를 건너는 가장 빠른 시간은 190초이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $-B$와 $P$가 주어진다. $B$는 다리의 수, $P$는 사람의 수이며, 두 값 모두 20을 넘지 않는다. (첫 번째 값을 음수 $-B$로 주는 것은 데이터를 구분하기 쉽게 하기 위해서이다.)

이어지는 $B$개의 줄에는 각 다리의 정보가 건너야 하는 순서대로 한 줄에 하나씩 주어진다. 각 줄에는 두 양의 정수 $C$와 $T$가 주어지며, $C$는 그 다리를 한 번에 건널 수 있는 최대 인원, $T$는 그 다리를 건너는 데 걸리는 시간이다. $C$는 최대 5, $T$는 최대 100이다. 최대 $C$명으로 이루어진 한 그룹이 다리를 건너는 데 걸리는 시간은 그룹 인원 수와 관계없이 항상 $T$이다.

입력의 마지막 줄에는 $0$ $0$이 주어지며, 이 줄은 처리하지 않는다.

정글의 법칙

문제

입력

출력