すまない

想定解は Python3 で TLE しました。PyPy3 で提出すると AC できることは確認しています。

問題文

ken さんと koo さんは、2 人でチームを組んで「飲酒競技プログラミングコンテスト (Inshu Competitive Programming Contest; ICPC)」に参加することにしました。

ICPC は $N$ 問の問題からなるコンテストで、以下の行動を何回か行うことでより多くの問題を解くことを目指します。

• チームメンバーの誰か一人が飲酒をする。そして、まだ解いていない問題を 1 つ選び、その問題を解く。

各チームメンバーには貢献度が決まっており、ken さんが $i$ 回 $(0 \le i \le N)$ 飲酒をした後の貢献度は $A_i$、koo さんが $i$ 回 $(0 \le i \le N)$ 飲酒をした後の貢献度は $B_i$ です。

また各問題には難易度が決まっており、$i$ 番目 $(1 \le i \le N)$ の問題の難易度は $D_i$ です。難易度が $D_i$ の問題は、その時点でのチームメンバーの貢献度の総和が $D_i$ 以上ならば解くことができます。

各チームメンバーの貢献度と各問題の難易度がわかっているとき、最適な戦略を取った場合最大で何問の問題を解けるかを求めてください。

入力

$N$
$A_0 \ A_1 \ \ldots \ A_N$
$B_0 \ B_1 \ \ldots \ B_N$
$D_1 \ D_2 \ \ldots \ D_N$

1 行目に問題の個数を表す整数 $N$ が与えられます。

2 行目に $N+1$ 個の整数が半角スペース区切りで与えられ、その内の $i+1$ 番目 $(0 \le i \le N)$ の整数 $A_i$ は、ken さんが $i$ 回の飲酒をした直後の貢献度の値を表します。

3 行目に $N+1$ 個の整数が半角スペース区切りで与えられ、その内の $i+1$ 番目 $(0 \le i \le N)$ の整数 $B_i$ は、koo さんが $i$ 回の飲酒をした直後の貢献度の値を表します。

4 行目に $N$ 個の整数が半角スペース区切りで与えられ、その内の $i$ 番目 $(1 \le i \le N)$ の整数 $D_i$ は、$i$ 番目の問題の難易度の値を表します。

入力は全部で $4$ 行となり、以下の制約を満たします。

• 入力は全て整数
• $1 \le N \le 3{,}000$
• $-10^5 \le A_i, B_i \le 10^5$
• $A_{i} \ge A_{i+1}$
• $B_{i} \ge B_{i+1}$
• $1 \le D_i \le 2 \times 10^5$

出力

解くことのできる問題数の最大値を出力してください。

サンプル

4
5 3 0 -1 -2
5 4 1 0 -3
5 7 4 8

3

5
100 0 -100 -200 -300 -400
8 7 6 5 4 3
5 6 7 8 9

5

1
1000 -1000
1000 -1000
1

0

8
34 8 8 -31 -32 -52 -54 -60 -62
87 71 46 42 8 -2 -35 -41 -52
53 25 15 36 82 79 58 36

6