자동차 여행

친구들이 저마다 다른 도시에 살고 있어서, 그 도시를 차례로 들르는 자동차 여행을 계획하고 있다. 연료비는 꼭 필요한 만큼만 쓰고 싶은데 도시마다 연료 가격이 달라서, 비용을 최소로 줄이려면 계획을 잘 세워야 한다. 값이 싼 도시에서 연료를 넉넉히 넣어 두면 비싼 도시에서 덜 사도 되고, 어떤 도시에서는 남은 연료를 되팔아 비용을 일부 회수하는 편이 낫다. 물론 연료 탱크에 담을 수 있는 양은 정해져 있고, 각 도시에서는 다음 도시까지 갈 만큼의 연료를 반드시 확보해야 한다. 다음 도시에 탱크가 빈 채로 도착해도 괜찮다.

여행 계획을 세우는 프로그램을 작성하라.

입력은 여러 여행의 정보로 이루어진다. 각 여행의 정보는 연료 탱크 용량 $c$(리터 단위, $0 < c < 100$)와 방문할 도시의 수 $t$($0 < t < 20$)가 적힌 줄로 시작한다. 0이 두 개 적힌 줄이 나오면 입력이 끝난다.

이어지는 $t$개의 줄에는 여행의 각 구간 정보가 순서대로 주어진다. 각 줄에는 그 구간이 시작되는 도시에서 연료 1리터를 사거나 파는 가격 $p$(달러와 센트 두 자리의 고정소수점 표기, $0.01 \le p < 9.99$)와 다음 도시까지 가는 데 필요한 연료의 양 $n$(정수, $1 \le n < 100$)이 주어진다. 사는 가격과 파는 가격은 같다.

모든 구간은 반드시 도달할 수 있다. 즉 $n$은 $c$를 넘지 않는다.

여행마다 한 줄씩 출력한다. 먼저 Journey k: 형식으로 여행 번호를 적고, 공백 한 칸을 둔 다음 그 여행을 마치는 데 드는 최소 비용을 소수점 아래 두 자리 고정소수점으로 출력한다. $k$는 1부터 세는 여행 번호이다.