어? 금지

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 시각마다 그 시각에서 b_i 이내에 외친 적이 없어야 한다는 조건 아래, 외칠 시각을 골라 혼란 c_i의 합을 최대로 만든다.

문제

'어?'

팀 대회 중 주변에서 '어?'라는 말이 들리면 마음이 혼란해진다. 그렇다고 해서 '어?'를 남발하면 혼란보다는 짜증이 앞서게 된다. 이를 잘 알고 있는 성우는 적당한 선을 지키면서 대회장에 최대한 큰 혼란을 주려고 한다.

대회는 시각 $0$ 에 시작한다.
성우가 '어?'를 외칠 수 있는 시각은 $N$ 개가 있고, $i$ 번째 시각은 $t\_i$ 다. $(1 \leq i \leq N)$
만약 성우가 시각 $t\_i$ $t_i$ 에 '어?'를 외치려 한다면, 성우는 시각 $(t\_i - b\_i)$ $(t_i - b_i)$ 부터 지금까지 '어?'를 외친 적이 없어야 한다.
- 성우가 정확히 시각 $(t\_i - b\_i)$ 에 '어?'를 외쳤더라도 시각 $t\_i$ 에 '어?'를 외칠 수 없다.

성우가 시각 $t\_i$ 에 '어?'를 외치면 대회장에 $c\_i$ 만큼의 혼란이 가해진다. 최종 혼란은 대회장에 가해진 혼란의 합이다.

성우는 대회장에 줄 수 있는 최종 혼란의 최댓값이 궁금해졌다. 성우를 위해 이를 구해주자.

첫 번째 줄에 성우가 '어?'를 외칠 수 있는 시각의 개수 $N$ 이 주어진다. $(1 \leq N \leq 100\\, 000)$

두 번째 줄에 정수 $t\_1, t\_2, \cdots , t\_N$ 이 공백을 사이에 두고 주어진다. $(1 \leq t\_i \leq 10^9\ ;\ t\_{i-1} < t\_i)$

세 번째 줄에 정수 $b\_1, b\_2, \cdots , b\_N$ 이 공백을 사이에 두고 주어진다. $(1 \leq b\_i \leq 10^9\ ;\ b\_i \leq t\_i)$

네 번째 줄에 정수 $c\_1, c\_2, \cdots , c\_N$ 이 공백을 사이에 두고 주어진다. $(1 \leq c\_i \leq 10^9)$

첫 번째 줄에 성우가 대회장에 줄 수 있는 최종 혼란의 최댓값을 출력한다.