Một người nông dân muốn cắt một thanh gỗ có độ dài của mình thành miếng, mỗi miếng có độ dài là một số nguyên dương . Tuy nhiên để cắt một miếng gỗ có độ dài là thành hai phần thì ông ta sẽ mất tiền. Ông nông dân này không giỏi tính toán lắm , vì vậy bạn được yêu cầu lập trình giúp cho ông ta biết cần để dành ít nhất bao nhiêu tiền thì mới có thể cắt được những tấm gỗ như mong muốn.
Dữ liệu vào:
Dòng đầu chứa số nguyên dương là số miếng gỗ cần cắt;
Dòng thứ hai chứa số nguyên là độ dài các miếng gỗ cần cắt thành.
Hai số liên tiếp trên cùng một dòng được ghi cách nhau một dấu cách.
Dữ liệu ra:
Một số nguyên duy nhất là tổng chi phí để cắt thành N miếng gỗ trên.
Ví dụ:
Dữ liệu vào:
4
1 2 3 4
Dữ liệu ra:
19
Giải thích:
Miếng gỗ có độ dài là cắt thành hai miếng và (chi phí là );
Cắt miếng độ dài thành hai miếng và (chi phí là );- Cắt miếng độ dài thành hai miếng và (chi phí là );
