Vào sinh nhật lần thứ 13, cậu bé Nam đã được cha đưa đi một chuyến du lịch trên biển. Thế nhưng, không may một trận bão đã khiến con tàu của họ lật úp. Khi tỉnh dậy, Nam nhận ra mình đang ở trên một hòn đảo hoang. Do ảnh hưởng từ cha – một nhà thám hiểm – Nam quyết định không bỏ cuộc và bắt đầu cuộc sống sinh tồn trên đảo bằng cách săn thú để kiếm thịt, hái trái cây, và ngủ dưới những gốc cây lớn để trú ẩn qua đêm.

Thời gian trôi qua, Nam bắt đầu nhận ra những dấu hiệu kỳ lạ trên đảo: các loài động vật trở nên hung hăng bất thường. Cậu cảm thấy rằng cần phải rời khỏi hòn đảo càng sớm càng tốt. Trong khi đi dọc bờ biển, Nam phát hiện ra N chiếc thuyền. Kiểm tra qua, cậu thấy rằng tất cả đều có thể sử dụng được. Quyết tâm rời khỏi đảo, Nam quyết định sử dụng những chiếc thuyền này để đến một hòn đảo khác có thể nhìn thấy từ xa.

Nam muốn mang theo tất cả thuyền để dự phòng trong trường hợp cần chúng trên hòn đảo tiếp theo. Để tiết kiệm thời gian, cậu có thể kéo cùng lúc 2 chiếc thuyền, với thời gian di chuyển bằng thời gian của chiếc thuyền chậm hơn trong hai chiếc. Hãy giúp Nam tìm cách di chuyển các thuyền để có thể vận chuyển tất cả đến hòn đảo bên kia trong thời gian ngắn nhất.

Có N chiếc thuyền được đánh số từ 1 đến N. Mỗi chiếc thuyền i (với 1 \leq i \leq N) cần thời gian T_i (phút) để di chuyển từ đảo A đến đảo B (hoặc ngược lại). Nam muốn vận chuyển tất cả thuyền từ đảo A sang đảo B trong thời gian ngắn nhất có thể.

Một lần, Nam có thể kéo tối đa 2 chiếc thuyền một lúc, với thời gian di chuyển bằng thời gian của chiếc thuyền chậm hơn. Ví dụ, nếu kéo cùng lúc một chiếc thuyền mất 2 phút và một chiếc mất 4 phút, thời gian di chuyển sẽ là 4 phút. Nếu kéo hai chiếc thuyền đều mất 3 phút, thời gian sẽ là 3 phút. Thời gian cần thiết để quay lại đảo A sau mỗi lần vận chuyển có thể bỏ qua.

• Dòng đầu tiên chứa số nguyên N – số lượng thuyền.
• Dòng thứ hai chứa N số nguyên T_i (cách nhau bởi khoảng trắng), với mỗi T_i là thời gian để di chuyển chiếc thuyền thứ i từ đảo A sang đảo B (hoặc ngược lại).

In ra tổng thời gian ngắn nhất (phút) để Nam có thể vận chuyển tất cả thuyền từ đảo A đến đảo B.

• 1 \leq N \leq 1000
• 1 \leq T_i \leq 10000