Американские горки
Бесси отправилась в путешествие и катается на американских горках! Ей очень нравится кататься, но, к сожалению, она часто испытывает головокружение.
Американские горки состоят из нескольких участков, которые Бесси проезжает по порядку. В начале поездки уровень её головокружения и веселья равен 0. На каждом участке Бесси может либо держать глаза открытыми, либо закрытыми (и должна держать их так на протяжении всего участка). Если она держит глаза открытыми, её общее веселье увеличивается на фактор веселья для этого участка, а головокружение — на фактор головокружения. Если же она держит глаза закрытыми, её общее веселье не изменится, но головокружение уменьшится на постоянное значение для всех участков. (Обратите внимание, что уровень головокружения никогда не может быть ниже 0.)
Если в какой-то момент головокружение Бесси превышает определённый предел, она заболеет. Напишите программу, чтобы определить максимальное количество веселья, которое Бесси может получить, не заболев.
Входные данные
Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается со строки с тремя целыми числами:
N K L
Где N (1 ≤ N ≤ 1000) — количество участков на американских горках, K (1 ≤ K ≤ 500) — величина, на которую уровень головокружения Бесси уменьшится, если она закроет глаза на любом участке, и L (1 ≤ L ≤ 300000) — предел головокружения, который Бесси может выдержать. Если её головокружение когда-либо станет больше L, Бесси заболеет, а это не весело!
Каждая из следующих N строк описывает участок американских горок и содержит два целых числа:
F D
Где F (1 ≤ F ≤ 20) — увеличение общего веселья Бесси, если она будет держать глаза открытыми на этом участке, и D (1 ≤ D ≤ 500) — увеличение уровня её головокружения, если она будет держать глаза открытыми на этом участке. Участки перечислены в порядке следования. Входные данные заканчиваются строкой с тремя 0.
Выходные данные
Для каждого тестового случая выведите одно целое число, представляющее максимальное количество веселья, которое Бесси может получить на этих американских горках, не превышая предел головокружения. Выведите каждое число на отдельной строке без пробелов. Не выводите пустые строки между ответами.