34662번 - 월향 수목원

문제

월향 수목원은 최근 $N$개의 식물을 심었다. 초기에 식물들은 아직 영양분을 받지 못한 상태다.

$i$번 식물은 $A_i$ 만큼의 영양분을 받으면 완전히 성장하며, 완전히 성장한 다음 날부터 구간 $[\max(1,i-R_i),\min(N,i+R_i)]$에 속한 식물들에 영양분을 매일 $V_i$ 만큼 공급하기 시작한다.

월향 수목원의 관리자인 아이보리가 매일 모든 식물에 1ドル$만큼의 영양분을 준다고 할 때, 모든 식물이 완전히 성장하기 위해서는 적어도 며칠이 걸리는지 구해보자.

입력

첫째 줄에 정수 $N$이 주어진다. $(1\leq N \leq 200,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 정수 $A_i, R_i, V_i$ 가 공백으로 구분되어 주어진다. $(1 \leq A_i, V_i \leq 200,000円; 1\leq R_i \leq N)$

출력

모든 식물이 완전히 성장하는 데 필요한 최소 일수를 출력한다.

제한

노트