30621번 - 어? 금지

문제

'어?'

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

• 대회는 시각 0ドル$에 시작한다.
• 성우가 '어?'를 외칠 수 있는 시각은 $N$개가 있고, $i$번째 시각은 $t_i$다. $(1 \leq i \leq N)$
• 만약 성우가 시각 $t_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)$

출력

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

제한

힌트