정올국에는 '뚫기'라는 게임이 유행 중이다. 게임은 가로 길이 N, 세로 길이 M의 직사각형의 가장 왼쪽에서 시작하여, 비행선을 조종해 장애물을 뚫거나 피해서 끝까지 가면 된다.

장애물은 세로 모양의 선분으로 표현할 수 있으며, 가로를 x축, 세로를 y축이라고 했을 때 한 x좌표에 최대 하나의 장애물만 있다.

여러분의 비행선은 기본적으로 +x축 방향으로 움직이고 있다. 장애물을 피하기 위해 세로 방향으로 움직일 수 있는데, 이떄 움직인 위치와 거리와는 상관없이 항상 A만큼의 연료를 사용한다. 또, B만큼의 연료를 사용하여 장애물을 뚫고 지나갈 수도 있다.

여러분의 목표는 모든 장애물을 지나 직사각형의 가장 오른쪽으로 가는 것이다. 최소한의 연료를 사용하여 목표를 달성해보자.

하지만 A와 B의 값은 그날그날 비행선의 상태에 따라 달라지기 때문에, 총 Q개의 A와 B쌍이 주어졌을 때 각각에 대한 최소 연료를 구해보자.

뚫기 timer 5s memory 2048MB

뚫기 5s 2048MB