꺾이지 않는 마음 2
시간 제한1.5초메모리 제한1024 MB
k가 1부터 N일 때까지, 도적이 하루에 최대 한 마리의 용을 쏴서 처음 k일 동안 얻을 수 있는 길이 합의 최댓값을 각각 구한다.
문제
"N = 10000 ×10 은 괜찮다. 중요한 것은 꺾이지 않는 마음"
당신의 농장에는 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 ≤ 100,000)
이후 N개의 줄에 걸쳐 각 용의 정보가 두 정수 D[i], H[i]로 주어진다. (0 ≤ D[i] ≤ 106, 0 ≤ H[i] ≤ 1012)
출력
N개의 줄을 출력하라. i번째 줄에는, k = i 일 때 문제의 정답을 하나의 정수로 출력하라.