Problem 3: Tile Exchanging [Ray Li]
Фермер Джон хочет покрыть пол в своем амбаре коллекцией квадратных плиток, которые он купил в магазине. К несчастью, Он не измерял точно размер своего амбара перед покупкой, поэтому сейчас он должен обменять часть плиток на другие, тоже квадратные, но других размеров.
N квадратных плиток которые ФД купил изначально имеют длины сторон A1...AN. Он хочет обменять часть из этих плиток так, чтобы общая сумма площадей всех плиток была ровно M.
При этом необходимо соблюсти правила обмена, установленные магазином: - плитка со стороной с длиной Ai может быть обменяна на другую плитку со стороной с длиной Bi за цену (Ai-Bi)* (Ai-Bi). Однако менять можно только ранее купленные плитки. Нельзя Менять плитку, полученную в результате обмена некоторой из ранее купленных плиток. Например, нельзя обменять плитку со стороной 3 на плитку со стороной 2 и потом плитку со стороной 2 поменять на плитку со стороной 1.
Определите минимальное количество денег, которое требуется ФД, чтобы сделать сумму площадей плиток равной M. Выведите –1, если невозможно получить площадь M.
PROBLEM NAME: tilechng
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N (1<=N<=10) и M (1<=M<=10,000).
* Строки 2..1+N: Каждая строка содержит одно целое число (от A1 до AN, описывающих длины сторон входных квадратных плиток (1<=Ai<=100).
Формат выходных данных
* Строка 1: Минимальная стоимость обменов чтобы получить площадь M, или –1, если получить площадь M невозможно.
Примечание
Обменяем первую плитку со стороной 3 на плитку со стороной 2 square, а вторую плитку со стороной 3 на плитку со стороной 1. Это дает суммарную площадь 4+1+1=6 за цену 4+1=5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 6
3
3
1
|
5
|