В магазине каждый товар имеет цену. Например, цена одного цветка равна 2 рубля, а цена одной вазы равна 5 рублей. Чтобы привлечь покупателей, магазин ввел скидки.

Скидка заключается в том, чтобы продавать набор одинаковых или разных товаров по пониженной цене. Например, три цветка за 5 рублей вместо 6, если покупать цветки по отдельности, или две вазы вместе с одним цветком за 10 рублей вместо 12 если покупать все по отдельности.

Сформулируем задачу в более общем виде. Пусть имеется М наборов, для которых действует система скидок. Каждый набор j, j=1,...M, характеризуется стоимостью ВM_j и соответствующим количеством товара в наборе (j₁,j₂,j₃,j₄, j₅). Покупка определяется набором Р=(р₁,р₂,_р3,р₄, р₅), где значение p_i, i=1,...,5 задает, сколько единиц товара должно находиться в корзине (1£p_i£5). Оптимальное решение должно быть получено посредством скидок. Набор товаров, который требуется купить, нельзя дополнять ничем, даже если бы это снизило общую стоимость набора.

Напишите программу, вычисляющую наименьшую цену, которую покупатель должен заплатить за заданную покупку.

Обратите внимание, что общее количество товаров в корзине может быть не более 5*5=25 единиц. Поэтому можно рассмотреть функцию С(i1,i2,i3,i4,i5), 0£i1,i2,i3,i4,i5£5, и вычислить для нее наилучшие решения. Понятно, что С(0,0,0,0,0) равно 0. Вначале полагаем, что все остальные значения - достаточно большие числа (например, максимальная стоимость товара, умноженная на 25). Значения этих чисел должны обладать тем свойством, что их значения должны быть больше оптимального решения. После того, как начальные значения С определены, необходимо последовательно вычислить значения функции, используя для этого все возможные скидки. Поэтому, если имеется М наборов со стоимостью В_j и соответствующим количеством товара в наборе (j₁,j₂,j₃, j₄,j₅), то

С(i1,i2,i3,i4,i5)= min{С(i1-j1, i2-j2, i3-j3, i4-j4,i5-j5) +Вj},

где минимум берется по всем наборам, для которых величины

i1-j1, i2-j2, i3-j3, i4-j4,i5-j5 - неотрицательные числа.