시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB4301046429.630%

문제

"N = 10000은 괜찮다. 중요한 것은 꺾이지 않는 마음"

당신의 농장에는 N마리의 용이 자라고 있다. 각 용은 1부터 N까지 서로 다른 번호가 붙어 있다. 오늘을 1일이라고 할 때, 1일의 i번 용의 키는 H[i] 이다. 하루가 바뀌는 시점에 모든 용의 키가 D[i] 만큼 증가한다.

농장 밖에는 당신의 용을 탐하는 도둑이 날카로운 마법 화살로 용을 훔치려고 하고 있다. 도둑은 매일 최대 하나의 마법 화살을 쏠 수 있으며, 도둑이 쏜 마법 화살은 도둑이 원하는 용에 정확히 맞는다. 도둑이 마법 화살을 i번 용에 적중시켰다면, i번 용의 키는 0이 되며, 도둑은 마법 화살의 힘을 빌어 잘린 길이 (즉, 원래 용의 키) 만큼의 용 조각을 얻는다. 도둑은 마법 화살을 쏘지 않을 수도 있으며, 한번 마법 화살을 적중시킨 용에 나중에 다시 화살을 적중시킬 수도 있다.

당신의 용들은 마법 화살에 잘릴지언정 그 마음은 꺾이지 않는다. i번 용의 키가 0이 되었다 하더라도, 다음 날이 될 때 다시 키가 D[i] 만큼 증가할 것이다.

모든 1 ≤ k ≤ N에 대해, 도둑이 1일부터 k일까지 매일 최대 한 번 화살을 쏠 수 있다고 가정할 때 얻은 용의 길이 합의 최댓값을 구하여라.

입력

첫 번째 줄에 용의 수 N이 주어진다. (1 ≤ N ≤ 10,000)

이후 N개의 줄에 걸쳐 각 용의 정보가 두 정수 D[i], H[i]로 주어진다. (0 ≤ D[i] ≤ 106, 0 ≤ H[i] ≤ 1012)

출력

N개의 줄을 출력하라. i번째 줄에는, k = i 일 때 문제의 정답을 하나의 정수로 출력하라.

예제 입력 1

3
7 15
3 5
1 5

예제 출력 1

15
27
42

출처

  • 문제를 번역한 사람: koosaga