Американські гірки#1385
Бессі вирушила у подорож і катається на американських гірках! Бессі дуже подобається кататися на них, але, на жаль, вона часто відчуває запаморочення.
Американські гірки складаються з кількох унікальних ділянок, які Бессі проходить по порядку. На початку поїздки рівень запаморочення і задоволення Бессі дорівнюють . На кожній ділянці гірок Бессі може тримати очі відкритими або закритими (і повинна тримати їх так весь відрізок). Якщо на ділянці вона тримає очі відкритими, рівень її задоволення збільшується на значення цієї ділянки, а запаморочення — на значення цієї ділянки. Якщо ж на ділянці вона тримає очі закритими, рівень її задоволення не змінюється, але запаморочення зменшується на певну константу, яка однакова для всієї поїздки. (Зауважимо, що запаморочення не може опуститися нижче .)
Якщо в якийсь момент рівень запаморочення Бессі перевищить певну межу, їй стане зле. Напишіть програму, яка визначить, яку максимальну кількість задоволення може отримати Бессі на гірках і при цьому не перевищити допустимий рівень запаморочення.
Вхідні дані містять кілька тестових випадків. Кожен тестовий випадок починається з рядка з трьома цілими числами:
N K L
де (1 \leq N \leq 1000) — кількість ділянок гірок, (1 \leq K \leq 500) — на скільки зменшиться запаморочення Бессі, якщо вона триматиме очі закритими на ділянці, (1 \leq L \leq 300000) — максимальний рівень запаморочення, який Бессі здатна витримати. Якщо в якийсь момент запаморочення перевищить , Бессі стане зле.
У наступних рядках описані ділянки гірок. Кожен такий рядок містить два цілих числа:
F D
де (1 \leq F \leq 20) — наскільки збільшиться загальне задоволення Бессі, якщо вона триматиме очі відкритими на цій ділянці, а (1 \leq D \leq 500) — наскільки збільшиться запаморочення, якщо вона триматиме очі відкритими на цій ділянці. Ділянки подаються в порядку проходження. Вхідні дані завершуються рядком із трьох нулів.
Для кожного тестового випадку виведіть одне ціле число — максимальну кількість задоволення, яку може отримати Бессі, не перевищивши допустимий рівень запаморочення. Виводьте кожне число у окремому рядку без пробілів. Не виводьте порожніх рядків між відповідями.
Приклад 1