저렴한 여행

대륙을 가로지르는 고속도로를 달리는 장거리 버스 여행은 여러 날이 걸리므로, 호텔 숙박비가 여행 경비에서 큰 부분을 차지한다. 안전과 편의를 위해 버스는 낮에만 달리며 하루에 최대 800 km까지 이동할 수 있다. 여행 중 매일 밤(출발 지점과 도착 지점의 밤은 제외)은 노선을 따라 있는 호텔에서 보낸다.

지금까지는 호텔에서 묵는 밤의 수를 최소로 하도록 여행을 계획했다. 비용을 줄이기 위해, 여행사는 여행 기간이 길어지더라도 호텔 숙박비의 합이 가능한 한 작아지도록 계획하는 것이 이득인지 알고 싶어 한다.

노선은 한 방향으로만 이어지며 갈라지지 않는다. 버스는 노선의 각 지점을 정확히 한 번씩 지난다. 호텔은 출발 지점으로부터의 거리로 구분하며, 한 지점에는 호텔이 최대 하나만 있다. 출발 지점과 도착 지점에서는 밤을 보내지 않는다. 승객 수는 일정하고, 어느 호텔에서든 각 승객과 운전기사는 그 호텔의 제시 가격에 따라 하룻밤에 같은 금액을 낸다. 모든 호텔은 이들 전부를 수용할 수 있다.

길이가 800 km인 노선의 모든 구간에는 호텔이 적어도 하나 있으므로, 위 규칙을 지키는 여행은 항상 가능하다. (노선 전체 길이가 800 km 이하라면 버스는 한 번에 통과할 수 있고, 밤을 전혀 보내지 않는다.)

프로그램은 다음 두 가지 여행 계획을 구해야 한다.

• 가장 저렴한 여행: 호텔 숙박비의 합이 가능한 한 작다. 그런 계획이 여럿이면 묵는 밤의 수가 가장 적은 것을 고른다.
• 가장 짧은 여행: 호텔에서 묵는 밤의 수가 가능한 한 적다. 그런 계획이 여럿이면 숙박비의 합이 가장 작은 것을 고른다.

첫째 줄에 공백으로 구분된 두 양의 정수가 주어진다. 노선의 길이 $d$ (킬로미터 단위)와 호텔의 수 $h$이며, $d \le 16000$, $h \le 1000$이다.

다음 $h$개의 줄에는 각각 호텔 하나의 정보가 주어진다. 각 줄에는 공백으로 구분된 두 양의 정수, 즉 출발 지점으로부터 그 호텔까지의 거리(킬로미터 단위)와 그 호텔에서의 1인 1박 가격(최대 1000)이 주어진다. 호텔은 출발 지점으로부터의 거리가 증가하는 순서로 나열된다.

두 줄을 출력한다.

첫째 줄에는 가장 저렴한 여행에 대해 그 호텔 숙박비의 합과 묵는 밤의 수를 공백 하나로 구분하여 출력한다.

둘째 줄에는 가장 짧은 여행에 대해 그 호텔 숙박비의 합과 묵는 밤의 수를 공백 하나로 구분하여 출력한다.

(노선 전체 길이가 800 km 이하이면 밤을 전혀 보내지 않는 계획이 가능하며, 이때 숙박비의 합과 밤의 수는 모두 0이다.)