이사 대작전 - Part IV
면접 대비시간 제한1초메모리 제한128 MB
연료 탱크가 200리터인 트럭으로 출발지와 도착지에서 각각 절반을 채운 상태를 유지하며, 최대 100개의 주유소 가격을 고려해 최소 연료비를 구한다.
문제
워털루에서 대도시로 이사하기 위해 이삿짐 트럭을 빌리려고 합니다. 요즘 기름값이 워낙 비싸서, 이 큰 트럭을 운행하는 데 드는 기름값이 얼마나 나올지 미리 알아 두고 싶습니다.
트럭은 1km를 달릴 때마다 정확히 1리터의 기름을 소비합니다. 연료 탱크의 용량은 200리터입니다. 워털루에서 트럭을 빌릴 때 탱크는 절반, 즉 100리터가 차 있습니다. 대도시에서 트럭을 반납할 때도 탱크가 최소한 절반(100리터) 이상 차 있어야 하며, 그렇지 않으면 렌터카 회사가 기름값을 훨씬 비싸게 청구합니다. 기름값은 최대한 아끼고 싶지만, 가는 도중에 기름이 바닥나서는 안 됩니다.
입력
입력은 모두 정수입니다. 첫 번째 정수는 워털루에서 대도시까지의 거리(km)이며, 최대 10000입니다. 그 다음에는 경로상의 모든 주유소를 나타내는 최대 100개의 주유소 정보가, 워털루로부터의 거리가 감소하지 않는 순서(같은 거리 허용)로 주어집니다. 각 주유소 정보는 두 정수, 즉 워털루로부터 그 주유소까지의 거리(km)와 그 주유소에서 파는 기름 1리터의 가격으로 이루어집니다. 가격의 단위는 1센트의 1/10이며, 최대 2000입니다.
출력
워털루에서 대도시까지 가는 데 드는 기름값의 최솟값을 출력합니다. 가격이 1센트의 1/10 단위로 주어지므로, 출력값도 같은 단위의 정수입니다. 가는 도중에 기름이 바닥나지 않고서는 대도시에 도착하는 것이 불가능하다면 "Impossible"을 출력합니다.