Mã bài:
ve
Điểm:
2 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Có ~N~ người xếp hàng mua vé, được đánh số theo thứ tự từ ~1~ đến ~N~. Thời gian phục vụ bán vé cho người thứ ~i~ là ~t_i~. Mỗi người cần mua một vé nhưng được quyền mua tối đa hai vé, vì thế một số người có thể nhờ người đứng ngay trước mình mua hộ. Người thứ ~i~ nhận mua hộ vé cho người thứ ~i+1~ thì thời gian mua vé cho hai người là ~r_i~.
Yêu cầu
Tìm phương án sao cho ~N~ người đều có vé với thời gian ít nhất.
Dữ liệu vào
- Dòng thứ nhất ghi số nguyên dương ~N~ (~1<N \leq 2000~) </li>
- Dòng thứ hai ghi ~N~ số nguyên dương ~t_1, t_2, ..., t_n ~
- Dòng thứ ba ghi ~N-1~ số nguyên dương ~r_1, r_2, ..., r_{n-1}~
Dữ liệu ra
Một dòng duy nhất là tổng thời gian phục vụ bán vé
Sample Input
5
2 5 7 8 4
3 9 10 10
Sample Output
17
Bình luận