정글의 법칙

상근이는 정글의 법칙의 상근족 족장이다. 이번에 떠날 곳은 아마존이고, 아마존의 희원 부족을 만났다. 희원 부족은 높은 나무 위에서 사는 부족이다. 이 나무는 줄로 만든 다리로 연결되어 있다.

마을이 생긴 이래로 처음으로 외부인이 왔기 때문에, 희원 부족의 부족장은 오랜 고민끝에 용기를 내어 나무에 자신들이 만든 다리를 건널 수 있는 기회를 주기로 했다.

각각의 다리는 동시에 지나갈 수 있는 사람의 수가 제한되어 있다. 만약, 이보다 많은 사람이 지나간다면, 희원 부족은 매우 놀랄 것이다.

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

상근이는 희원 부족을 놀라게 하지 않으려고 한다. 이번 촬영은 다리를 최대한 빨리 건너는 것이다. 상근족의 족장 상근이는 희원 부족을 놀라게 하지 않기 위해서, 다음과 같은 두 가지 지시를 내렸다.

1. 한 번에 한 그룹!

어떤 다리를 두 명 또는 그 이상이 건널 수 있을 때는, 그 사람들은 한 그룹으로 정하고 동시에 다리를 건너게 한다. 이때, 다리가 무너지지 않게 하기 위해서 최대한 서로 붙어서 움직이고, 걸음걸이도 똑같이 맞추고 걷는다. 다리가 무너지지 않는다고 하더라도, 두 그룹이 동시에 같은 다리를 건널 수는 없다. 그 이유는 여러 그룹이 다리를 건너면 다리가 흔들리게 되고, 희원 부족은 매우 놀랄 것이다. 그룹의 구성원은 한 명이 될 수도 있다.

2. 계속 움직여!

만약, 건너는 사람이 없는 다리가 있다면, 최대한 많은 사람들이 그룹을 이루고 그 다리를 건너기 시작할 것이다. 물론, 이 방법은 다리를 가장 빠르게 건너는 방법은 아니다. 하지만, 희원 부족은 사람들이 다리를 건너지 않고 기다리고 있다면, 다리에 무슨 문제가 생긴 것으로 착각하고 매우 놀랄 수 있다.

다리의 정보와 사람의 수가 주어졌을 때, 위의 2가지 조건을 지키면서 모든 사람이 다리를 건너는데 드는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

예를 들어, 9명이 2개의 다리를 건너는 경우를 생각해보자. 첫 번째 다리는 동시에 3명이 10초만에 건너갈 수 있고, 두 번째 다리는 4명이 60초만에 건너갈 수 있다.

첫 번째 상태는 (9 0 0)으로 나타낼 수 있다. 이 상태의 뜻은 9명이 첫 번째 다리를 건너기 위해 기다리고 있고, 두 번째 다리를 건너기 위해 기다리는 사람과 모든 다리를 건너는 사람은 없다는 뜻이다.

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는 사람의 수이다. B와 P는 20을 넘지 않는다. (B가 음수로 주어지는 이유는 데이터를 구분하기 쉽게 하기 위해서이다) 다음 B개 줄에는 한 줄에 하나씩 다리의 정보가 주어진다. 입력으로 주어지는 다리를 순서대로 건너야 한다. 각 다리의 정보는 두 양의 정수 C와 T로 이루어져 있다. C는 동시에 건널 수 있는 사람의 수, T는 그 다리를 건너는데 드는 시간이다. C는 최대 5이고, T는 최대 100이다. 최대 C명으로 이루어진 한 그룹이 다리를 건너는 시간은 T이다. 이때, 그룹 구성원의 수와 걸리는 시간은 상관이 없다. 입력의 마지막 줄에는 0 0이 주어진다.

각 테스트 케이스에 대해서, 모든 사람이 상근이의 명령을 지키면서 다리를 건너는데 드는 가장 빠른 시간을 출력한다.