시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 64 36 14 37.838%

문제

승현이는 음이 아닌 정수 N개로 구성된 배열을 가지고 놀고 있다. 이 배열에는 M개의 특별한 조건이 있는데, 그것은 길이가 Li인 어떤 연속한 구간을 잡아도 합이 Si를 넘지 않는다는 것이다. 승현이는 특별한 조건을 모두 만족하는 배열을 모두 만들어 놓고, 1 이상 N 이하의 모든 정수 K에 대해 각 배열에서 길이가 K인 모든 연속한 구간마다 원소의 합을 구하고 그 중 가장 큰 것을 찾아보았다. 하지만 승현이는 계산에 자신이 없어서 자신이 잘 구했는지 확신하지 못하고 있다. 승현이가 올바르게 구했는지 알아보자.

입력

첫 번째 줄에 배열을 구성하는 정수의 개수 N(1 ≤ N ≤ 200, 000)과 특별한 조건의 개수 M(1 ≤ M ≤ 200)이 주어진다.

두 번째 줄부터 M 개의 줄에 걸쳐 특별한 조건을 의미하는 두 정수 Li 와 Si 가 주어진다. (1 ≤ i ≤ M, 1 ≤ Li ≤ N, 1 ≤ Si ≤ 109)

출력

N줄에 걸쳐 K번째 줄에 특별한 조건을 모두 만족하는 배열의 길이가 K인 연속한 구간들 중 합이 가장 큰 구간의 구간 합을 출력한다.

예제 입력 1

5 2
2 5
3 7

예제 출력 1

5
5
7
10
12

힌트

배열이 [1, 4, 1, 0, 5]일 때, 길이가 1인 연속한 구간들 중 합이 5인 것이 존재하고, 길이가 2인 연속한 구간들 중 합이 5인 것이 존재하고, 길이가 4인 연속한 구간들 중 합이 10인 것이 존재한다.

배열이 [3, 2, 2, 1, 4]일 때, 길이가 3인 연속한 구간들 중 합이 7인 것이 존재하고, 길이가 5인 연속한 구간들 중 합이 12인 것이 존재한다.