A. Что у нас на ужин?
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В одной малоизвестной, но очень красивой стране Ватерляндии обитает милая акула Валерия. Как и у всех акул, зубы у нее расположены в несколько рядов, а питается она преимущественно карасиками. Одной из отличительных особенностей Валерии является то, что поедая одного карасика, она использует только один ряд зубов, остальные зубы в это время «отдыхают».

Долго наша героиня бороздила морские просторы в поисках своих любимых карасиков, пока не произошло с ней большое несчастье. Однажды у Валерии разболелись зубы, и ей пришлось обратиться к местному стоматологу, омару Ашоту. Будучи профессионалом, Ашот очень быстро избавил Валерию от зубной боли. Кроме того, он сумел определить причину развившегося кариеса (за что впоследствии получил прозвище Кэп).

Оказалось, что Валерия кушает слишком много карасиков. Чтобы предостеречь акулу от повторного возникновения зубной боли, Ашот определил для каждого зуба Валерии его остаточную жизнеспособность. Остаточной жизнеспособностью зуба стоматолог назвал величину, равную числу карасиков, которых можно съесть, используя этот зуб. Каждый раз, когда Валерия будет съедать карасика, жизнеспособность всех зубов, задействованных при этом, будет уменьшаться на единицу, и как только жизнеспособность хотя бы одного зуба станет отрицательной, акуле вновь придется обратиться за помощью стоматолога.

Опечаленная этими известиями, Валерия вернулась домой, где ее уже поджидала порция заранее заготовленных карасиков. Конечно же, акула не могла отказаться от своей горячо любимой пищи, но желания вновь оказаться в стоматологическом кресле у Валерии также не было. Поэтому она решила, что съест максимальное число имеющихся у нее карасиков, но при этом такое, чтобы жизнеспособность никакого зуба не становилась отрицательной.

Поскольку Валерия не сильна в математике, она попросила вас помочь ей определить суммарное число карасиков, которыми она сможет отужинать.

Напомним, что при поедании одного карасика Валерия использует ровно один ряд зубов, причем жизнеспособность каждого зуба, принадлежащего этому ряду, уменьшается на единицу.

Входные данные

В первой строке задано три целых числа n, m, k (1 ≤ m ≤ n ≤ 1000, 0 ≤ k ≤ 106) — общее число зубов у Валерии, количество зубных рядов и количество карасиков, имеющихся у Валерии на ужин, соответственно. В следующих n строках содержится по два целых числа: r (1 ≤ r ≤ m) — номер ряда, которому принадлежит соответствующий зуб, и c (0 ≤ c ≤ 106) — его остаточная жизнеспособность.

Гарантируется, что в каждом ряду находится положительное число зубов.

Выходные данные

В первую строку выведите наибольшее число карасиков, которыми Валерия сможет поужинать.

Примеры
Входные данные
4 3 18
2 3
1 2
3 6
2 3
Выходные данные
11
Входные данные
2 2 13
1 13
2 12
Выходные данные
13