В ведении дорожно-ремонтного строительного управления (ДРСУ) находится K дорог. Дорога построена качественно и сама по себе не ломается, но время от времени другие службы вынуждены ломать асфальт на некоторых дорогах для доступа к коммуникациям. После такого вмешательства на дороге остаются ямы. От каждой дороги с ямой или несколькими в течение одного дня жители города получают одну единицу недовольства. Если ДРСУ отремонтирует дорогу с ямой в тот же день, когда она появилась, то будет получено ноль единиц недовольства. Если на дороге появилась яма в день i, а ремонт был произведен в день j, то будет получено j-i единиц недовольства. За один день ДРСУ может отремонтировать любое количество дорог.
На ближайший период известны даты проведения работ с коммуникациями и дороги, на которых они проводятся. Всего таких работ будет проведено N.
К сожалению, в бюджете ДРСУ достаточно средств только на M ремонтов. Определите, какое наименьшее количество недовольства получат жители города.
Формат входных данных
В первой строке вводятся числа K, N и M (1 ≤ K ≤ 1000, 1 ≤ N, M ≤ 100000) - количество дорог, количество работ и максимальное количество ремонтов соответственно.
В следующих N строках заданы пары чисел Di, Wi (1 ≤ Di ≤ 109, 1 ≤ Wi ≤ K) - день проведения работы и номер дороги, на которой эта работа производится. Пары заданы в порядке неубвывания Di.
Формат результата
Выведите одно число - минимальное суммарное недовольство жителей. Если после окончания периода останутся дороги с ямами - выведите -1 (признак бесконечного недовольства).
На ближайший период известны даты проведения работ с коммуникациями и дороги, на которых они проводятся. Всего таких работ будет проведено N.
К сожалению, в бюджете ДРСУ достаточно средств только на M ремонтов. Определите, какое наименьшее количество недовольства получат жители города.
Формат входных данных
В первой строке вводятся числа K, N и M (1 ≤ K ≤ 1000, 1 ≤ N, M ≤ 100000) - количество дорог, количество работ и максимальное количество ремонтов соответственно.
В следующих N строках заданы пары чисел Di, Wi (1 ≤ Di ≤ 109, 1 ≤ Wi ≤ K) - день проведения работы и номер дороги, на которой эта работа производится. Пары заданы в порядке неубвывания Di.
Формат результата
Выведите одно число - минимальное суммарное недовольство жителей. Если после окончания периода останутся дороги с ямами - выведите -1 (признак бесконечного недовольства).
