Roller Coaster
Bessi səyahətə çıxıb və o, roller coaster sürür! Bessi roller coaster sürməyi çox sevir, amma təəssüf ki, tez-tez başı gicəllənir.
Roller coaster-in Bessi ardıcıllıqla sürdüyü bir neçə fərqli hissəsi var. Sürüşün əvvəlində Bessinin başgicəllənmə və əyləncə səviyyələri hər ikisi 0-dır. Roller coaster-in hər bir hissəsi üçün Bessi ya gözlərini açıq saxlaya bilər, ya da bağlı saxlaya bilər (və bütün hissə boyunca bu şəkildə saxlamaq məcburiyyətindədir). Əgər o, bir hissə üçün gözlərini açıq saxlayarsa, ümumi əyləncəsi həmin hissənin Əyləncə faktoru qədər artır və başgicəllənməsi həmin hissənin Başgicəllənmə faktoru qədər artır. Lakin, əgər o, hissə üçün gözlərini bağlı saxlayarsa, ümumi əyləncəsi dəyişməyəcək, amma başgicəllənməsi bütün roller coaster üçün sabit olan bir dəyər qədər azalacaq. (Qeyd edək ki, onun başgicəllənməsi heç vaxt 0-dan aşağı düşə bilməz.)
Əgər hər hansı bir anda Bessinin başgicəllənməsi müəyyən bir həddən yuxarı olarsa, Bessi xəstələnəcək. Bessinin xəstələnmədən maksimum əyləncəni necə əldə edə biləcəyini tapmaq üçün bir proqram yazın.
Giriş verilənləri
Girişdə bir neçə test halı olacaq. Hər test halı üç tam ədəddən ibarət bir sətirlə başlayacaq:
N K L
Burada N (1 ≤ N ≤ 1000) bu roller coaster-dəki hissələrin sayıdır, K (1 ≤ K ≤ 500) Bessinin başgicəllənmə səviyyəsinin hər hansı bir hissədə gözlərini bağlı saxladığı zaman azalacağı miqdardır və L (1 ≤ L ≤ 300000) Bessinin dözə biləcəyi başgicəllənmə həddidir - əgər onun başgicəllənməsi heç vaxt L-dən böyük olarsa, Bessi xəstələnəcək və bu əyləncəli deyil!
Növbəti N sətirdən hər biri roller coaster-in bir hissəsini təsvir edəcək və iki tam ədəd olacaq:
F D
Burada F (1 ≤ F ≤ 20) Bessinin həmin hissədə gözlərini açıq saxladığı zaman əldə edəcəyi ümumi əyləncənin artımıdır və D (1 ≤ D ≤ 500) həmin hissədə gözlərini açıq saxladığı zaman başgicəllənmə səviyyəsinin artımıdır. Hissələr ardıcıllıqla veriləcək. Giriş üç 0 olan bir sətirlə bitəcək.
Çıxış verilənləri
Hər test halı üçün Bessinin başgicəllənmə həddini aşmadan həmin roller coaster-də əldə edə biləcəyi maksimum əyləncəni təmsil edən bir tam ədəd çıxarın. Hər tam ədədi öz sətirində boşluqsuz çap edin. Cavablar arasında boş sətir çap etməyin.