Задача №114931. Ещё одна акция
В знаменитом магазине «Двоечка» продукты продаются всего два дня в неделю — понедельник и вторник — причём в разные дни по разным ценам. Вы захотели купить \(n\) килограммов картофеля на неделю. По понедельникам один килограмм картофеля стоит \(a\) рублей, а по вторникам — \(b\) рублей. Чтобы упростить работу кассирам, в «Двоечке» можно покупать только целое число килограммов.
Вам крупно повезло, ведь в «Двоечке» проходит акция: каждый понедельник за каждые \(m\) килограммов купленного картофеля дарят ещё один!
Найдите минимальную сумму, за которую можно приобрести хотя бы \(n\) килограммов картофеля на неделю.
В первой строке вводится целое число \(a\) \((1 \leqslant a \leqslant 10^9)\) — цена одного килограмма картофеля в понедельник.
Во второй строке вводится целое число \(b\) \((1 \leqslant b \leqslant 10^9)\) — цена одного килограмма картофеля во вторник.
В третьей строке вводится целое число \(n\) \((1 \leqslant n \leqslant 10^9)\) — желаемое количество килограммов картофеля.
В четвертой строке вводится целое число \(m\) \((1 \leqslant m \leqslant 10^9)\) — количество килограммов картофеля, участвующее в акции.
Выведите одно целое число — минимальное число рублей, которое придется заплатить, чтобы купить хотя бы \(n\) килограммов картофеля.
Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.
В первом примере выгодно купить один килограмм в понедельник за 5 рублей, получить еще один килограм в подарок и купить килограмм во вторник за 4 рубля. Купить три килограмма дешевле не получится.
Во втором примере выгодно купить три килограмма в понедельник и получить один килограмм в подарок.
В третьем примере акцией пользоваться невыгодно.
В четвертом примере выгодно купить шесть килограммов в понедельник, получить по акции три килограмма и купить еще один килограмм во вторник.
В данной задаче \(38\) тестов, помимо тестов из условия. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Тесты разбиты на три группы. Проверка на тестах третьей группы проводится только при прохождении всех тестов первых двух групп. При этом баллы начисляются за каждый пройденный тест.
Тесты первой группы удовлетворяют условию \(m = 1\). Решения, корректно работающие на тестах этой группы, наберут не менее \(28\) баллов.
Тесты второй группы удовлетворяют условию \(n \leqslant 10^6\). Решения, корректно работающие на тестах этой группы, наберут не менее \(48\) баллов.
5 4 3 1
9
4 5 4 2
12
3 4 3 5
9
20 15 10 2
135
1000000000 900000000 1000000000 8
888888888900000000