Một trung tâm thương mại có $N$ món hàng, trong đó món thứ $i$ có giá là $A_i$. Hiện trung tâm đang có chương trình khuyến mãi “mua hai tặng một”, quy tắc cụ thể như sau: cứ mua $2$ món hàng, giả sử giá của món rẻ hơn là $P$ (nếu hai món có giá bằng nhau thì $P$ bằng giá của một trong hai món), thì có thể chọn tùy ý một món hàng có giá không vượt quá $\dfrac{P}{2}$ từ các món còn lại để nhận miễn phí món đó. Có thể mua lặp lại $2$ món hàng nhiều lần để nhận nhiều món miễn phí, nhưng mỗi món hàng chỉ có thể được mua hoặc nhận miễn phí một lần.

Minh muốn biết nếu muốn lấy hết tất cả các món hàng (bao gồm cả mua và nhận miễn phí) thì ít nhất phải tốn bao nhiêu tiền?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên, biểu thị $A_1,A_2,A_3,\dots,A_N$.

Dữ liệu ra

Xuất ra một số nguyên, biểu thị đáp án.

Ví dụ

Input

7
1 4 2 8 5 7 1

Output

25

Ghi chú

Phạm vi dữ liệu $1 \le N \le 5 \times 10^5$ $1 \le A_i \le 10^9$

Giải thích ví dụ Giải thích phương án mua: Minh có thể mua thành ba đợt: Trước tiên mua món giá $4$ và $8$, được tặng miễn phí món giá $1$; Tiếp theo mua món giá $5$ và $7$, được tặng miễn phí món giá $2$; Cuối cùng mua riêng món còn lại có giá $1$. Tổng chi phí tính được $(4 + 8 + 5 + 7 + 1 = 25)$, không tồn tại phương án nào có chi phí thấp hơn.