Фермер Джон только что получил N (1 <= N <= 20) упаковок сена, упаковка I имеет размер Si (1 <= Si <= 100). Он хочет разделить упаковки между тремя амбарами как можно более справедливо.
Под справедливостью он понимает минимальную разницу между максимальными значениями. То есть, если B1, B2, B3 - суммарные размеры всех упаковок, в амбарах 1 2 и 3 соответственно (где B1>=B2>=B3), то ФД хочет чтобы B1 был самым минимальным из всех возможных.
Например пусть есть 8 упаковок с размерами:
2 4 5 8 9 14 15 20
Справедливое решение есть:
Амбар 1: 2 9 15 B1 = 26 Амбар 2: 4 8 14 B2 = 26 Амбар 3: 5 20 B3 = 25
Пожалуйста, помогите ФД определить B1 справедливого распределения.
PROBLEM NAME: baleshare
Формат входных данных
* Строка 1: Количество упаковок, N.
* Строки 2..1+N: Строка i+1 содержит Si, размер i-ой упаковки.
Формат выходных данных
* Строка 1: Выведите значение B1 справедливого распределения упаковок
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
14
2
5
15
8
9
20
4
|
26
|