В одном популярном сервисе такси появилась возможность выбирать различные точки посадки. Даниилу очень нравится нововведение, так как теперь заказывать такси стало удобнее, а иногда и выгоднее. Вот и сейчас Даниил собирается воспользоваться услугами такси и раздумывает, в какой точке оптимальнее сесть в машину.
Даниил может вызвать такси непосредственно к своему дому или выбрать одну из $$$N$$$ альтернативных точек, куда можно подать машину.
Если Даниил вызывает такси к дому, то это обойдётся ему в $$$K$$$ рублей; после приезда такси Даниил сразу в него садится.
Если Даниил вызывает такси к $$$i$$$-й точке, то это будет стоить на $$$A_i$$$ рублей дешевле, чем вызов к дому, но водителю придётся ждать, пока Даниил дойдёт до нужного места (Даниил выходит из дома в момент, когда такси приедет). Чтобы добраться от дома до $$$i$$$-й точки, Даниилу требуется $$$B_i$$$ минут.
Стоимость ожидания клиента у такси фиксирована и составляет $$$M$$$ рублей за минуту.
Помогите Даниилу определить минимально возможную стоимость поездки.