산타클로스

곧 크리스마스다. 순록은 이미 매어졌고 산타클로스도 거의 출발할 준비를 마쳤지만, 선물은 아직 썰매에 다 싣지 못했다.

썰매에는 선물을 무한히 실을 수 있다. 하지만 무거운 썰매를 끄는 순록 무리는 금방 지친다. 그래서 선물은 가능한 한 적게 실어야 한다.

이를 알고 있던 꼬마 요정들은 산타클로스의 경로에 있는 집 지붕 위에 선물 창고를 설치했다.

산타클로스는 자기 집(출발점)에서든 어느 창고에서든 선물을 실을 수 있다.

산타클로스가 방문할 아이의 수가 주어질 때, 자기 집과 각 창고에서 썰매에 실어야 할 선물의 수를 구하라. 썰매에 실린 선물의 수는 언제나 최대한 적어야 한다.

산타클로스는 다음 규칙에 따라 움직인다.

• 집 번호가 작은 순서대로, 첫 번째 집부터 아이들을 방문한다.
• 모든 아이를 방문하기 전에는 썰매를 되돌릴 수 없다.
• 지붕에 창고가 있는 집에서는 먼저 창고에서 썰매를 선물로 채운 뒤, 그 집에 사는 아이에게 선물을 준다.

모든 아이는 서로 다른 집에 살며, 각 아이에게 선물을 하나씩 준다.

첫째 줄에 두 정수 $N$(아이의 수)과 $M$(선물 창고의 수)이 주어진다. 다음 $M$개 줄에는 각각 두 정수가 주어진다.

• $K_i$: 창고가 있는 지붕이 몇 번째 아이의 집 지붕인지 나타낸다. $K_i$는 증가하는 순서로 주어진다.
• $Z_i$: 그 창고에 있는 선물의 수.

시작점에 있는 산타클로스의 집에는 선물이 무한히 있다.

$M + 1$개의 정수를 서로 다른 줄에 출력한다. 첫째 줄에는 여행을 시작하기 전에 썰매에 미리 실어야 할 선물의 수를 출력한다. 이어지는 $M$개 줄에는 각 창고에서 실어야 할 선물의 수를 출력한다. 창고의 순서는 입력에 주어진 순서와 같다.

• $1 ≤ N ≤ 10\,000$
• $0 ≤ M ≤ N$
• $1 ≤ K_1 < \dots < K_i < K_{i+1} < \dots < K_M ≤ N$
• $1 ≤ Z_i ≤ 10\,000$