C - Make-Up Exam Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君と青木君は同じクラスに通っており、期末テストの結果で競い合っています。

期末テストは N 科目あり、各科目にはそれぞれ満点が設定されています。i 番目の科目の満点は P_i 点です。各科目の得点は 0 点以上 P_i 点以下の整数です。

テストの結果、高橋君は i 番目の科目で A_i 点を、青木君は i 番目の科目で B_i 点を獲得しました。

ここで、高橋君の全科目の合計得点から青木君の全科目の合計得点を引いた値を得点差と呼ぶことにします。高橋君は、この得点差をできるだけ大きくしたいと考えています。

先生の計らいにより、高橋君は N 科目の中から必ずちょうど 1 科目を選んで、その科目のテストをやり直すことができます。やり直した科目の高橋君の得点は、0 以上その科目の満点以下の任意の整数に変更されます。変更後の得点は元の得点と同じ値であっても構いません。なお、青木君の得点は変わりません。

高橋君が最適に科目を選び得点を設定し直したとき、やり直し後の得点差としてあり得る最大の値を求めてください。なお、この値は負になることもあります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • 0 \leq A_i \leq P_i
  • 0 \leq B_i \leq P_i
  • 入力はすべて整数である。

入力

N
P_1 P_2 \cdots P_N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
  • 1 行目には、科目数を表す整数 N が与えられる。
  • 2 行目には、各科目の満点を表す N 個の整数 P_1, P_2, \ldots, P_N がスペース区切りで与えられる。
  • 3 行目には、高橋君の各科目の得点を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • 4 行目には、青木君の各科目の得点を表す N 個の整数 B_1, B_2, \ldots, B_N がスペース区切りで与えられる。

出力

高橋君が最適に行動したときの、やり直し後の得点差の最大値を 1 行で出力せよ。

入力例 1

3
100 100 100
60 80 50
70 70 70

出力例 1

30

入力例 2

5
200 150 300 100 250
200 100 250 80 50
150 120 200 90 100

出力例 2

220

入力例 3

8
1000000000 500 1000 200 300 400 600 800
0 500 1000 200 300 400 600 800
1000000000 0 0 0 0 0 0 0

出力例 3

3800

Score : 300 pts

Problem Statement

Takahashi and Aoki are in the same class and competing based on their final exam results.

The final exam consists of N subjects, each with its own maximum score. The maximum score for the i-th subject is P_i points. The score for each subject is an integer between 0 and P_i, inclusive.

As a result of the exam, Takahashi scored A_i points and Aoki scored B_i points on the i-th subject.

Here, we define the score difference as the value obtained by subtracting Aoki's total score across all subjects from Takahashi's total score across all subjects. Takahashi wants to maximize this score difference.

Thanks to the teacher's arrangement, Takahashi can choose exactly 1 subject from the N subjects and retake that subject's exam. Takahashi's score on the retaken subject will be changed to any integer between 0 and that subject's maximum score, inclusive. The new score may be the same as the original score. Aoki's scores do not change.

When Takahashi optimally chooses the subject and sets his new score, find the maximum possible score difference after the retake. Note that this value may be negative.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9
  • 0 \leq A_i \leq P_i
  • 0 \leq B_i \leq P_i
  • All inputs are integers.

Input

N
P_1 P_2 \cdots P_N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
  • The first line contains an integer N representing the number of subjects.
  • The second line contains N integers P_1, P_2, \ldots, P_N separated by spaces, representing the maximum score for each subject.
  • The third line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing Takahashi's score for each subject.
  • The fourth line contains N integers B_1, B_2, \ldots, B_N separated by spaces, representing Aoki's score for each subject.

Output

Print in one line the maximum possible score difference after the retake when Takahashi acts optimally.

Sample Input 1

3
100 100 100
60 80 50
70 70 70

Sample Output 1

30

Sample Input 2

5
200 150 300 100 250
200 100 250 80 50
150 120 200 90 100

Sample Output 2

220

Sample Input 3

8
1000000000 500 1000 200 300 400 600 800
0 500 1000 200 300 400 600 800
1000000000 0 0 0 0 0 0 0

Sample Output 3

3800