[http://online-judge.uva.es/p/v102/10201.html 원문보기]
----
=== 이 문제는 ===
인기도:A(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:3(1~4)

=== About [AdventuresInMoving:PartIV] ===
워털루에서 대도시로 이사를 가려고 하는데, 이삿짐 트럭을 빌려서 갈까 생각 중이다. 그런데 요즘 기름 값이 하도 비싸서 가는데 기름 값이 얼마 정도 들지 미리 계산해보고자 한다.

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

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

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

=== Sample Input ===
{{{~cpp 
1

500
100 999
150 888
200 777
300 999
400 1009
450 1019
500 1399
}}}
=== Sample Output ===
{{{~cpp 
450550
}}}

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

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

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