Сережа — хозяин ресторана вместительностью n человек. Как и полагается, в холле ресторана есть вешалка с n крючками. Каждый посетитель ресторана может воспользоваться крючком и повесить на него свою одежду. Стоимость использования i-го крючка — ai рублей. На один крючок может повесить одежду только один человек.
Сегодня вечером к Сереже в ресторан придут m гостей. Естественно, что каждый гость хочет повесить свои вещи на еще незанятый крючок с минимальной стоимостью (если таких крючков несколько, то на любой такой). Однако если в момент, когда придет очередной гость, на вешалке не будет свободных крючков, Сережа должен заплатить гостю штраф в размере d рублей.
Помогите Сереже узнать прибыль в рублях, возможно отрицательную, которую он получит за сегодняшний вечер. Считайте, что перед приходом гостей вешалка полностью свободна, все гости приходят в разное время, никто кроме m гостей не посещает ресторан Сережи в этот вечер.
Примечание
В первом тесте после прихода всех гостей обе вешалки будут заняты, поэтому Сережа получит прибыль 1 + 2 = 3 рублей.
Во втором тесте после прихода всех гостей обе вешалки будут заняты, но и Сережа заплатит штраф 8 раз, поэтому его прибыль составит 3 - 8 = - 5 рублей.