У вас есть три кучи сладостей, состоящие из красных, зеленых и синих конфет:
- первая куча состоит только из \(r\) красных конфет,
- вторая куча состоит только из \(g\) зеленых конфет,
- третья куча состоит только из \(b\) синих конфет.
Каждый день Таня съедает ровно две конфеты различных цветов. Она выбирает любые цвета конфет, единственное ограничение - она не может съесть две конфеты одного цвета за один день.
Найдите максимальное количество дней, в течение которых Таня может есть сладости. Каждый день Таня должна съедать ровно две конфеты.
Выходные данные
Выведите \(t\) целых чисел: \(i\)-е число соответствует ответу на \(i\)-й набор данных.
Примечание
В первом примере Таня может есть конфеты только в течение одного дня. Она может съесть любую пару конфет, потому что все они различного цвета.
Во втором примере Таня может есть конфеты в течение двух дней. Например, она может съесть красную и зеленую конфету в первый день и зеленую и синюю конфету во второй день.
В третьем примере Таня может есть конфеты в течение двух дней. Например, она может съесть красную и зеленую конфету в первый день и красную и синюю во второй день. Заметьте, что две красные конфеты остались не съедены.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1 1
1 2 1
4 1 1
7 4 10
8 1 4
8 2 8
|
1
2
2
10
5
9
|