Sweet Problem
Contest: Codeforces Round 603 (Div. 2)
Difficulty rating: 1100
Tags: math

You have three piles of candies: red, green and blue candies:

- the first pile contains only red candies and there are $$$r$$$ candies in it,
- the second pile contains only green candies and there are $$$g$$$ candies in it,
- the third pile contains only blue candies and there are $$$b$$$ candies in it.

Each day Tanya eats exactly two candies of different colors. She is free to choose the colors of eaten candies: the only restriction that she can't eat two candies of the same color in a day.

Find the maximal number of days Tanya can eat candies? Each day she needs to eat exactly two candies.

Input format:
The first line contains integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each test case is given as a separate line of the input. It contains three integers $$$r$$$, $$$g$$$ and $$$b$$$ ($$$1 \le r, g, b \le 10^8$$$) — the number of red, green and blue candies, respectively.

Output format:
Print $$$t$$$ integers: the $$$i$$$-th printed integer is the answer on the $$$i$$$-th test case in the input.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, Tanya can eat candies for one day only. She can eat any pair of candies this day because all of them have different colors.

In the second example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and green and blue candies on the second day.

In the third example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and red and blue candies on the second day. Note, that two red candies will remain uneaten.

Example input:
6
1 1 1
1 2 1
4 1 1
7 4 10
8 1 4
8 2 8

Example output:
1
2
2
10
5
9

Editorial:
Sort the values of $$$r$$$, $$$g$$$, $$$b$$$ such that $$$r \geq g \geq b$$$. Now consider two cases.
If $$$r \geq g + b$$$, then Tanya can take $$$g$$$ candies from piles $$$r$$$ and $$$g$$$, and then — $$$b$$$ candies from piles $$$r$$$ and $$$b$$$. After that there may be a bunch of candies left in the pile $$$r$$$ that Tanya won't be able to eat, so the answer is $$$g + b$$$.
Otherwise, we need to achieve the equality of the piles $$$r$$$, $$$g$$$, $$$b$$$. First, we make equal $$$r$$$ and $$$g$$$ by eating $$$r - g$$$ from the piles $$$r$$$ and $$$b$$$ (this can always be done since $$$r < g + b$$$). Then we make equal the piles $$$g$$$, $$$b$$$ by eating $$$g - b$$$ from the piles $$$r$$$ and $$$g$$$. After that, $$$r = g = b$$$, and we can get three different cases.
• $$$r = g = b = 0$$$ — nothing needs to be done, Tanya has already eaten all the sweets;
• $$$r = g = b = 1$$$ — you can take candy from any of two piles so in the end there will always be one candy left;
• $$$r = g = b \geq 2$$$ — we reduce all the piles by $$$2$$$, taking, for example, a candy from piles $$$r$$$ and $$$g$$$, $$$g$$$ and $$$b$$$, $$$r$$$ and $$$b$$$. With such actions, Tanya eventually reaches the two previous cases, since the sizes of the piles are reduced by 2.
Since with this strategy we always have 0 or 1 candy at the end, Tanya will be able to eat candies for $$$\lfloor \frac{r + g + b}{2} \rfloor$$$ days.