Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P192SUMC - Bốc bi

Time limit: 1s

Okami được mời tham dự vào game show “bốc bi trúng thưởng”. Cách chơi của game show đó như sau:

-         Chương trình sẽ đưa ra 2*N viên bi được xếp thành 2 hàng mỗi hàng N viên, trên mỗi viên bi được đánh 1 số tự nhiên không âm.

-         Người chơi sẽ phải lựa chọn bi theo luật của chương trình (được trình bày phía dưới).

-         Số tiền mà người chơi nhận được sẽ bằng tống các số ghi trên những viên bi mà người này chọn.

Luật chọn bi như sau:

-         Người chơi sẽ chọn bi từ trái sang phải.

-         Chỉ số của từng viên bi được chọn (không bao gồm viên bi đầu tiên được chọn) sẽ lớn hơn chỉ số của viên bi đã chọn trước đó.

-         Không được chọn 2 viên bi liên tiếp thuộc cùng 1 hàng

-         Có thể chọn số lượng bi bất kỳ.

Hãy giúp Okami giành được nhiều tiền nhất trong game show này nhé!!!!

Input

-         Dòng đầu tiên ghi số nguyên N (1 <= N <= 10^5).

-         Dòng thứ hai gồm N số nguyên h11,h12,…,h1n (1 <= h1i <= 10^9) – h1i các số ghi trên viên bi thứ i tại hàng 1.

-         Dòng thứ ba gồm N số nguyên h21,h22,…,h2n (1 <= h2i <= 10^9) – h2i các số ghi trên viên bi thứ i tại hàng 2.

Output

-         Gồm 1 số nguyên duy nhất là kết quả của bài toán.

Example

Input

Ouput

5

9 3 5 7 3

5 8 1 4 5

29

Giải thích:


Được gửi lên bởi:adm
Ngày:2019-07-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2019-07-24 14:38:32
Simple dp.
2019-07-23 16:56:47
giống bài QBSELECT ý
2019-07-22 09:22:04
ai cho tui ý tưởng với
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.