Anh Khoai làm người ở cho lão phú hộ, lão hứa cứ làm ăn chăm chỉ lão gả con gái cho. Sau ba năm anh Khoai chăm chỉ làm ăn làm giầu ú ụ cho lão phú hộ. Lão định nuốt lời đem gả con gái cho nhà phú ông khác bèn nói nếu anh Khoai tìm được cây tre 100 đốt sẽ gả con gái cho.

Anh Khoai đi khắp cách rừng không tìm được cây tre nào như vậy. Vừa đói vừa mệt anh thiếp đi thấy một ông già râu tóc bạc phơ nói anh cứ đi chặt 100 đốt tre về sẽ có cách ghép thành cây.

Anh Khoai đi chặt được n đoạn tre có số đốt lần lượt là \(a_1,a_2,...a_n\) được ông già hướng dẫn đọc thần chú "Khắc nhập, Khắc nhập" kỳ lạ thay các đoạn tre ghép ngay lại với \(n-1\) khớp nối thành 1 cây tre rất dài.

Anh Khoai phát hiện ra rằng nếu khớp nối giữa 2 đoạn có số đốt chẵn với lẻ hoặc lẻ với chẵn thì không sao nhưng cứ khớp nối giữa 2 đoạn cùng số đốt chẵn hoặc số đốt lẻ sẽ bị rút bớt một đốt.

Bạn hãy giúp anh Khoai nối thế nào để sau khi nối số đốt là nhiều nhất nhé

Input

Dòng đầu gồm số nguyên dương n có giá trị không vượt quá 100 là số đoạn tre

Dòng tiếp theo chứa n số nguyên dương là số đốt tương ứng của n đoạn tre có giá trị không vượt quá \(1000\)

Output

Một số nguyên dương duy nhất là số đốt nhiều nhất có thể có được của cây tre, biết rằng bạn có thể đảo trật tự các đoạn để cây tre đạt được số đốt nhiều nhất

Ví dụ 1

Input

4
8 6 4 8

Output

23

Ví dụ 2

Input

3
8 6 7

Output

21

Ví dụ 3

Input

3
5 5 7

Output

15