Петя решил торговать на бирже. Он знает цену покупки, и цену продажи акций в каждый из следующих N дней. Изначально на торговлю у Пети есть K рублей. Определите наибольшую сумму в рублях, которую может заработать Петя, если он может ровно один раз купить акции и ровно один раз их продать. По правилам биржи между покупкой и продажей акций должно пройти не менее T дней. При этом разрешается продавать и покупать только целое число акций (например, если у вас есть 5 рублей, а акция стоит 2 рубля, то вы можете купить не более двух акций).
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит три целых числа N, T и K (1 ≤ N ≤ 108, 1 ≤ T ≤ 106 , 1 ≤ K ≤ 106). Следующие N строк содержат пары чисел, обозначающих цену покупки и цену продажи одной акции. Каждое из чисел натуральное, не превосходящее 106. В первой строке содержатся цены за первый день, во второй строке – цены за второй день и тд.
Типовой пример организации данных во входном файле
4 2 100
3 10
80 90
70 75
100 20
При таких исходных данных выгодно купить 33 акции в первый день и продать их в предпоследний день. Заработок составит 75*33 - 3*33 = 2376.
