Lật bài
Bạn được cho $N$ quân bài có 2 trạng thái úp hoặc ngửa. Khởi đầu game, tất cả các quân bài đều đang ở trạng thái úp. Mỗi lượt đi bạn sẽ lật ngửa đúng 1 lá bài và lá bài đã lật thì không thể tác động lên nó nữa. Ngoài ra, với mỗi quân bài khi lật, sẽ tăng thêm cho bạn một số điểm nhất định tùy thuộc vào trạng thái 2 quân bài (nếu có) cạnh nó. Cụ thể với là bài thứ $i$ như sau:
- Tăng $a_i$ điểm nếu không có quân bài nào cạnh nó ở trạng thái ngửa;
- Tăng $b_i$ điểm nếu có đúng 1 quân bài cạnh nó đã ngửa;
- Tăng $c_i$ điểm nếu có đúng 2 quân bài cạnh nó đã ngửa.
Nhiệm vụ của bạn là tìm một cách lật các lá bài sao cho số điểm có được là lớn nhất. Tìm và in ra giá trị đó.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N \ (0<N\le10^5)$;
- Dòng thứ hai chứa $N$ số nguyên $a_i \ (0\le a_i\le10^9)$;
- Dòng thứ ba chứa $N$ số nguyên $b_i \ (0\le b_i\le10^9)$;
- Dòng thứ tư chứa $N$ số nguyên $c_i \ (0\le c_i\le10^9)$.
Kết quả
- Kết quả bài toán.
Chấm điểm
20;$N\le10$ 30;$N\le20$. 20;$c_i=0;$ chỉ tồn tại một vị trí $a_i \neq 0$. 30;Không còn giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
4
1 2 3 4
4 3 2 1
0 1 1 0
output
13
Giải thích
Lật lần lượt các lá bài $4,3,2,1$.
Comments