CS_034 TRỒNG CÂY

Trong dự án định cư trên Sao Hỏa, Việt đã nghiên cứu thành công một giống cây đặc biệt có khả năng giải phóng khí Oxi khi được tưới nước. Việt tiến hành trồng N cây thành một hàng thẳng và đánh số thứ tự từ 1 đến N . Qua thực nghiệm, Việt phát hiện ra một điều thú vị: Lượng Oxi mà một cây tạo ra không chỉ phụ thuộc vào bản thân nó mà còn phụ thuộc vào thời điểm nó được tưới so với các cây lân cận. Cụ thể, lượng Oxi thu được từ cây thứ i được tính như sau:

• Trường hợp 1: Nếu tại thời điểm cây i được tưới, cây bên cạnh i - 1 và i + 1 đều chưa được tưới nước, lượng Oxi tạo ra là A_i.

• Trường hợp 2: Nếu tại thời điểm cây i được tưới, có đúng một trong hai cây bên cạnh đã được tưới nước trước đó, lượng Oxi tạo ra là B_i .

• Trường hợp 3: Nếu tại thời điểm cây i được tưới, cây bên cạnh i - 1 và i + 1 đều đã được tưới nước trước đó, lượng Oxi tạo ra là C_i.

Quy ước: Cây số 1 và cây số N chỉ có duy nhất một cây bên cạnh. Do đó, chúng chỉ có thể rơi vào Trường hợp 1 (cây bên cạnh chưa tưới) hoặc Trường hợp 2 (cây bên cạnh đã tưới). Tất cả N cây đều sẽ được tưới nước một lần, nhưng thứ tự tưới giữa các cây có thể thay đổi để tối ưu tổng lượng Oxi.

Yêu cầu: Hãy giúp Việt xác định tổng lượng Oxi lớn nhất thu được từ tất cả các cây.

Dữ liệu vào có cấu trúc như sau:

• Dòng thứ nhất: Gồm một số nguyên dương N .

• Dòng thứ hai: Gồm N số nguyên dương A1, A2, ..., A_N.

• Dòng thứ ba: Gồm N số nguyên dương B1, B2, ..., B_N.

• Dòng thứ tư: Gồm N số nguyên dương C1, C2, ..., C_N.

Dữ liệu ra ghi một số nguyên duy nhất là tổng lượng Oxi tối đa tìm được.

Ví dụ:

INPUT

3

1 2 3

3 4 5

5 6 7

OUTPUT

10

Giới hạn:

• Có 30% số test 1 <= N <=8.

• 30\% số test 8 < N <=20.

• 20\% số test 20 < N < 10^3.

• 20\% số test 10^3 < N <= 10^5.

• Các giá trị Ai, Bi, C_i đều là các số nguyên dương không vượt quá 10^9.