Maximum Coins from Dragons

A brave knight has encountered several dragons. Each dragon holds a certain number of coins. The knight can only choose exactly two dragons and take half (rounded down) of the coins from each chosen dragon.

Problem: Given \(N\) dragons with coin counts \(c_1, c_2, \dots, c_N\), when a dragon with \(c_i\) coins is chosen, the knight gets \(\left\lfloor \frac{c_i}{2} \right\rfloor\) coins. The knight wishes to maximize the total coins collected by choosing two dragons. Formally, if dragons \(i\) and \(j\) are chosen, the number of coins collected is \[ \left\lfloor \frac{c_i}{2} \right\rfloor + \left\lfloor \frac{c_j}{2} \right\rfloor, \] find the maximum possible sum.

inputFormat

The first line contains an integer \(N\) (\(2 \leq N \leq 10^5\)), representing the number of dragons.

The second line contains \(N\) space-separated integers \(c_1, c_2, \dots, c_N\), where each \(c_i\) denotes the number of coins in the \(i\)-th dragon.

outputFormat

Output a single integer representing the maximum coins that can be collected by selecting two dragons and taking half of the coins (rounded down) from each.

4
8 15 7 10

12