Có một thanh bánh dài \(N\) milimét, trong đó \(N\) là số chẵn. Hai người có liên quan đến JOI quyết định cắt thanh bánh thành nhiều đoạn rồi chia nhau, sao cho mỗi người nhận được các đoạn có tổng chiều dài là \(N/2\) milimét.

Không rõ vì sao, độ dễ cắt của thanh bánh lại khác nhau tùy theo vị trí. Hai người đã kiểm tra từng vị trí cách nhau \(1\) milimét tính từ đầu trái và xác định số giây cần để cắt tại mỗi vị trí.

Yêu cầu

Hãy viết chương trình tính tổng thời gian cắt ít nhất, tính bằng giây, để hai người có thể chia thanh bánh như trên.

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

• Dòng đầu tiên chứa số nguyên chẵn \(N\), là chiều dài thanh bánh tính bằng milimét.
• Dòng thứ \(i+1\) (\(1\le i\le N-1\)) chứa số nguyên \(t_i\), là số giây cần để cắt tại vị trí cách đầu trái \(i\) milimét.

Lưu ý rằng chỉ có \(N-1\) vị trí có thể cắt.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa tổng số giây ít nhất cần để cắt thanh bánh cho hai người chia nhau.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
• \(2\le N\le10000\).
• \(N\) là số chẵn.
• \(1\le t_i\le10000\) (\(1\le i\le N-1\)).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(1\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

• \(5\%\) số điểm dành cho các dữ liệu mà thời gian nhỏ nhất có thể đạt được bằng cách cắt tại không quá \(2\) vị trí.
• \(10\%\) số điểm dành cho các dữ liệu mà thời gian nhỏ nhất có thể đạt được bằng cách cắt tại không quá \(3\) vị trí.
• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le20\).

Ví dụ

6
1
8
12
6
2

7