Koi có rất nhiều khối đồ chơi hình lập phương, hôm nay cậu muốn xây một tòa tháp vừa vững chắc vừa đẹp bằng cách chồng các khối lên nhau.

Để tháp được chắc chắn cậu muốn khối ở dưới phải có thể tích không nhỏ hơn khối ở trên. Đồng thời để tháp được "đẹp" cậu muốn hai khối liên tiếp phải khác tính chẵn lẻ.

Chiều cao của tháp được tính bằng tổng các cạnh của những khối làm nên tháp đó.

Cho một dãy số nguyên dương là độ dài cạnh các khối đồ chơi của Koi, hỏi Koi có thể xây tòa tháp vững chắc và đẹp cao tối đa bao nhiêu?

Ví dụ: Koi có các khối cạnh \(3\), \(6\), \(5\), \(3\), \(1\), \(1\) thì cậu có thể xây tòa tháp như ý muốn với chiều cao tối đa là \(11 (= 6 + 5)\).

Đầu vào

Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 10^5)\) là số khối đồ chơi mà Koi có.

Dòng thứ hai gồm \(n\) số nguyên dương trong đoạn \([1, 10^9]\) là cạnh các khối đồ chơi của Koi.

Đầu ra

Một số tự nhiên duy nhất là kết quả bài toán.

Subtask

\(30\%\) số test có \(n \le 10\).

\(30\%\) số test có \(10 < n \le 1000\).

Ví dụ

Đầu vào:

6
3 6 5 3 1 1

Đầu ra:

11