В известной сети гипермаркетов Heap-Hop ежегодно проводится следующая акция.
В декабре при покупке любого товара стоимостью не меньше 1 000 руб., за каждую целую тысячу рублей в стоимости одного товара выдаётся купон номиналом в 500 руб. Например, если мы покупаем в декабре один товар стоимостью 1 001 руб., а второй — 2 999 руб., то получим купон в 500 руб. за первый и всего два купона за второй. В январе полученные купоны можно использовать для оплаты 20% стоимости уже всей покупки в целом. То есть вне зависимости от стоимости отдельных товаров, если в январе общая сумма покупки в нашем примере будет не меньше 7 500 руб., то 1 500 мы оплатим купонами, а если меньше, то мы не сможем использовать все купоны полностью. Но даже за покупку стоимостью меньше 500 руб. мы сможем получить скидку в 20%, отдав купон номиналом 500 руб.
Семья Бережливых давно присмотрела ряд товаров в одном из гипермаркетов этой сети. Зная условия акции, они решили распределить покупки на два месяца так, чтобы в итоге заплатить за все товары вместе как можно меньше. Младший сын Бережливых Иван взялся написать программу, которая и выдаст соответствующие рекомендации, но родители не уверены, что его программа будет находить минимально возможную сумму денег, которой можно обойтись при покупке всех необходимых товаров с учётом акции. Поэтому подобную программу предлагается написать вам.