주유

어떤 운송업자가 자동차로 $A$ 도시에서 $B$ 도시까지 화물을 나른다. 경로를 따라 여러 주유소가 있고, 주유소마다 휘발유를 서로 다른 가격에 판다. 맨 처음 주유소는 경로의 시작 지점($A$ 도시)에 있다.

모든 자동차는 $1$마일마다 정확히 $1$단위의 휘발유를 쓰지만, 자동차마다 연료 탱크의 용량이 다르다. $A$에서 $B$까지 가는 데 드는 비용은 탱크 용량과 주유 계획에 따라 달라진다. 모든 주유소에는 어떤 자동차의 탱크든 가득 채울 만큼 충분한 휘발유가 있으며, 주유소들은 모든 자동차가 $A$에서 $B$까지 갈 수 있도록 배치되어 있다 (연속한 두 주유소 사이의 거리와 마지막 주유소에서 $B$까지의 거리는 모두 탱크 용량 이하이다).

자동차는 탱크가 빈 상태로 $A$에서 출발한다. 탱크 용량과 주유소들의 가격 및 간격이 주어질 때, $A$에서 $B$까지 운전하는 데 필요한 휘발유의 최소 총비용을 구하라.

첫째 줄에 탱크 용량을 나타내는 정수 $p$가 주어진다 ($1 \le p \le 10^{6}$).

둘째 줄에 $A$에서 $B$까지의 경로에 있는 주유소의 개수를 나타내는 정수 $n$이 주어진다 ($1 \le n \le 10^{6}$).

이어지는 $n$개의 줄에는 각각 두 양의 정수 $c_i$와 $d_i$가 공백 하나로 구분되어 주어진다. 주유소는 $A$에서 멀어지는 순서대로 번호가 매겨진다. $c_i$는 $i$번째 주유소에서 휘발유 $1$단위의 가격이고, $d_i$는 $i$번째 주유소와 $i+1$번째 주유소 사이의 거리(마일)이다 (마지막 값 $d_n$은 마지막 주유소에서 $B$까지의 거리이다). 값들은 $1 \le c_i \le 1000$과 $1 \le d_i \le 10^{6}$을 만족한다. 경로 전체의 길이(모든 $d_i$의 합)는 $10^{6}$ 이하이다.

주어진 탱크 용량을 가진 자동차가 $A$에서 $B$까지 운전하는 데 드는 최소 주유 비용을 정수 하나로 출력한다.