Hàng năm, vương quốc tổ chức một khảo nghiệm gọi là "Con đường đế vương". Có ~n~ cửa ải, mỗi cửa ải anh hùng cần phải chiến đấu với một con quái vật có lượng HP (máu) là ~a_i~. Để giết chết một con quái vật thì anh hùng sẽ cần tiêu hao một lượng thể lực tương ứng với lượng HP của nó.

Để hỗ trợ các anh hùng và khảo nghiệm cả trí thông minh của họ, Nữ thần chiến tranh đã đưa ra thêm một quy tắc như sau: Nếu lượng thể lực tiêu hao khi giết một con quái vật lớn hơn hoặc bằng ~1500~ thì anh hùng sẽ được lựa chọn một trong hai loại bùa chú hỗ trợ:

• Bùa chú suy yếu sau khi sử dụng lên quái vật sẽ khiến chúng mất một nửa HP (nếu lượng HP là số lẻ thì làm tròn xuống kết quả).
• Bùa chú công kích sẽ gây ~1000~ sát thương lên quái vật (nếu lượng HP của quái vật ban đầu bé hơn hoặc bằng 1000, quái vật sẽ chết luôn và anh hùng không tốn hao thể lực).

Mỗi cửa ải, anh hùng chỉ có thể sử dụng 1 tấm bùa, còn lại phải dựa hoàn toàn vào thể lực để chém giết quái vật. Một con quái vật đã bị suy yếu hoặc công kích bởi bùa chú vẫn có thể cung cấp phần thưởng nếu lượng thể lực tiêu hao để giết nó vẫn thoả mãn yêu cầu. Bùa chú có thể được tích luỹ.

Yêu cầu

Cho số lượng của ải và lượng HP của quái vật tại từng cửa ải. Hãy tính tổng lượng thể lực tiêu hao thấp nhất để anh hùng có thể vượt qua toàn bộ cửa ải (thể lực di chuyển giữa các cửa ải được coi như bằng 0).

Input

• Dòng đầu tiên chứa 1 số nguyên dương ~n~ ~(1≤n≤150)~ là số lượng cửa ải cần thông qua trên "Con đường đế vương".
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1≤a_i≤5000)~, lần lượt là lượng HP của từng con quái vật ở mỗi cửa ải.

Output

• Một dòng duy nhất chứa một số nguyên là tổng lượng thể lực tiêu hao ít nhất mà anh hùng cần tiêu hao để chinh phục "Con đường đế vương".

Sample Input

5
1000 1500 900 3000 1500

Sample Output

5400

Giải thích

Giết con quái vật thứ nhất cần ~1000~ thể lực.

Giết con quái vật thứ hai cần ~1500~ thể lực, lựa chọn loại bùa chú suy yếu.

Giết con quái vật thứ ba cần ~900~ thể lực.

Sử dụng bùa chú suy yếu rồi giết con quái vật thứ tư cần ~1500~ thể lực, lựa chọn loại bùa chú sát thương.

Sử dụng bùa chú sát thương rồi giết con quái vật thứ năm cần ~500~ thể lực.

Tổng thể lực tiêu hao là ~5400~.

Subtask

• Có 50% số test ứng với 50% số điểm có ~1≤n≤20~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.