Хетаг уже несколько дней ничего не ел (да и не спал), потому что занимается подготовкой вступительной олимпиады в кружок по программированию. К сожалению, ни один человек не может прожить столько времени совсем без еды, поэтому пришла пора подкрепиться.

Готовить, разумеется, времени особо нет — надо писать условия к задачам! Но можно заказать доставку. Сейчас набирает популярность сервис «У нас есть еда!», который отличается очень гибкой политикой цен на доставку. Сейчас Хетаг сделал заказ на x0
рублей, и доставка для него стоит a0 рублей, таким образом за заказ он заплатит x0+a0
рублей.

Однако, если заказ достигнет x1>x0
рублей, доставка станет стоить a1 рублей, при стоимости заказа хотя бы x2 рублей, доставка стоит a2 рублей, и так далее. Всего их ценовая политика предусматривает k+1 способ сделать заказ, последний из которых заключается в доставке за ak рублей при стоимости заказа от xk
рублей включительно.

Хетаг готов заказать еще любое количество детских наборов в дополнение к своему заказу, каждый из наборов стоит b
рублей. Помогите ему посчитать какую минимальную сумму он может заплатить суммарно за заказ и доставку!

Входные данные
В первой строке дано два целых числа x0
и a0 — исходные стоимости заказа и доставки (0⩽x0,a0⩽106).
Во второй строке дано число k
— количество дополнительных ценовых политик сервиса (1⩽k⩽200000). В i-й из следующих k строк через пробел даны числа xi и ai — граница стоимости заказа, с которой действует новая ценовая политика доставки, и стоимость доставки в этом случае (xi−1 В последней строке дано единственное целое число b
— стоимость детского набора, которым Хетаг может неограниченно дополнять свой заказ (1⩽b⩽106).

Выходные данные
Выведите единственное целое число — минимальную суммарную стоимость заказа и доставки, которую может получить Хетаг, возможно дополнив свой изначальный заказ детскими наборами.