인기도:A(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:3(1~4)

워털루에서 대도시로 이사를 가려고 하는데, 이삿짐 트럭을 빌려서 갈까 생각 중이다. 그런데 요즘 기름 값이 하도 비싸서 가는데 기름 값이 얼마 정도 들지 미리 계산해보고자 한다.
이 트럭은 1킬로미터를 가는 데 1리터의 기름이 필요하다. 기름통은 200리터다. 워털루에서 트럭을 빌릴 때는 기름통이 절반만큼 차 있다. 나중에 대도시에서 차를 반납할 때도 기름은 절반 이상 채워 놓아야 한다. 그렇게 하지 않으면 렌탈 회사에 훨씬 비싼 비용을 지불해야 한다. 기름 값은 최대한 아끼고 싶지만, 그렇다고 해서 길 위에서 기름이 바닥나서 멈춰서는 일은 없도록 해야 한다.

첫 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 입력되며, 그 다음 줄은 빈 줄이다. 각 테스트 케이스는 정수만으로 구성된다. 첫번째 정수는 워털루에서 대도시까지의 거리를 킬로미터 단위로 표시한 것으로, 최대 10,000이다. 그 밑으로는 출발지로부터 거리가 가까운 것부터 먼 것 순서로, 주유소에 대한 정보가 입력되며, 최대 100개까지 입력될 수 있다. 각 주유소에 대해 워털루로부터의 거리(킬로미터 단위)와 휘발유 1리터당 가격(0.1센트 단위)이 입력된다. 리터당 휘발유 값은 최대 2,000(즉 200센트 = 2달러)이다. 서로 다른 테스트 케이스 사이에는 빈 줄이 입력된다.

각 테스트 케이스에 대해 워털루에서 대도시까지 가는 데 드는 연료비의 최소 값을 출력한다. 문제의 제약조건에 따를 때 워털루에서 대도시까지 갈 수 없으면 "Impossible"이라고 출력한다. 서로 다른 테스트 케이스에 대한 결과 사이에는 빈 줄을 출력한다.

~cpp 
1

500
100 999
150 888
200 777
300 999
400 1009
450 1019
500 1399

~cpp 
450550

작성자	사용언어	개발시간	코드
문보창	C++	2일	AdventuresInMoving:PartIV/문보창
김상섭	C++	2주일	AdventuresInMoving:PartIV/김상섭

음. 나중에 대도시에서 차를 반납할 때도 기름은 절반 이상 채워 놓아야 한다. 여기서 절반 이상이라는 조건에 주의를 하지 않으면 안됩니다. -- 보창

위의 테스트 케이스를 보면 처음에는 거리가 100인 주유소에 무조건 가야합니다. 그러면 기름은 0이 되고, 스터디때 말한 방법으로 하면 앞의 200까지를 살피고, 가장 작은 가격이 있는 곳인 (200, 777) 까지 갈 수 있는 기름 100을 넣고 출발합니다. 그러나 여기서 살펴보면 최적의 해는 여기서 50만큼의 기름만 넣고, 150의 지점에서 또 50의 기름을 넣어서 (200,777)에 가는 경우입니다. -- 보창
----
문제분류 / 경시대회준비반