Американські гірки
Бессі вирушила в подорож і катається на американських гірках! Вона дуже любить ці атракціони, але часто відчуває запаморочення.
Американські гірки складаються з кількох секцій, які Бессі проходить по черзі. На початку поїздки рівні запаморочення та задоволення Бессі дорівнюють 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.
Вихідні дані
Для кожного тестового випадку виведіть одне ціле число, яке представляє максимальну кількість задоволення, яке Бессі може отримати на цих американських гірках, не перевищуючи межу запаморочення. Надрукуйте кожне число в окремому рядку без пробілів. Не друкуйте порожніх рядків між відповідями.