Có \(N\) viên ngọc. Giá trị của viên ngọc thứ \(i\) là \(V_i\).

Bạn sẽ chọn một số viên ngọc này, có thể là tất cả hoặc không chọn viên nào, và lấy chúng.

Tuy nhiên, bạn cần phải trả một chi phí \(C_i\) để lấy viên ngọc thứ \(i\).

Gọi \(X\) là tổng giá trị của các viên ngọc đã lấy, và \(Y\) là tổng chi phí đã trả.

Tìm giá trị lớn nhất có thể của \(X - Y\).

Ràng buộc

• Tất cả các giá trị đầu vào là số nguyên.
• \(1 \leq N \leq 20\)
• \(1 \leq C_i, V_i \leq 50\)

INPUT FORMAT

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

N
V_1
V_2
...
V_N
C_1
C_2
...
C_N

OUTPUT FORMAT

In ra giá trị lớn nhất có thể của \(X - Y\).

Ví dụ:

Input

3
10 2 5
6 3 4

Output

5

Nếu chúng ta chọn viên ngọc thứ nhất và thứ ba, \(X = 10 + 5 = 15\) và \(Y = 6 + 4 = 10\). Ta có \(X - Y = 5\) ở đây, là giá trị lớn nhất có thể.

Input

4
13 21 6 19
11 30 6 15

Output

6

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  3 10 2 5 6 3 4

• Giải thích:

  • Chọn viên ngọc thứ nhất và thứ ba, tổng giá trị là 15 và tổng chi phí là 10, nên giá trị lớn nhất của \(X - Y\) là 5.

Ví dụ 2:

• Input:

  4 13 21 6 19 11 30 6 15

• Giải thích:

  • Chọn viên ngọc nào đó, giá trị tối đa của \(X - Y\) có thể đạt được là 6, tính từ tổng giá trị và chi phí.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House