Roller Coaster#1385
Bessi səyahətə çıxıb və hazırda roller coaster-dədir! Bessi roller coaster-də getməyi çox sevir, amma təəssüf ki, tez-tez başı hərlənir.
Roller coaster bir-birinin ardınca keçilən bir neçə fərqli hissədən ibarətdir. Gəzintinin əvvəlində Bessinin başgicəllənməsi və əyləncə səviyyələri hər ikisi -dır. Roller coaster-in hər hissəsi üçün Bessi ya gözlərini açıq tutmalı, ya da bağlı saxlamalıdır (və bu hissənin sonuna qədər bu qaydaya riayət etməlidir). Əgər Bessi bu hissədə gözlərini açıq tutarsa, ümumi əyləncə səviyyəsi həmin hissənin Əyləncə göstəricisi qədər artır, başgicəllənməsi isə həmin hissənin Başgicəllənmə göstəricisi qədər artır. Lakin əgər gözlərini bağlı tutarsa, ümumi əyləncə səviyyəsi dəyişməz, amma başgicəllənməsi bütün gəzinti üçün sabit olan bir dəyər qədər azalır. (Qeyd: başgicəllənmə heç vaxt -dan aşağı olmur.)
Əgər istənilən vaxtda Bessinin başgicəllənməsi müəyyən limitdən artıq olarsa, Bessi xəstələnəcək. Beləliklə, Bessinin xəstələnmədən roller coaster-də əldə edə biləcəyi maksimum əyləncə səviyyəsini müəyyən edən proqram yazın.
Giriş bir neçə test halından ibarətdir. Hər bir test halı bir sətirdə üç tam ədəddən ibarət olmaqla başlayır:
N K L
Burada (1 \leq N \leq 1000) roller coaster hissələrinin sayıdır, (1 \leq K \leq 500) Bessi bu hissədə gözlərini bağlasa başgicəllənmənin azalacağı miqdardır və (1 \leq L \leq 300000) Bessinin dözümlü başgicəllənmə həddidir. Əgər başgicəllənmə -i keçərsə, Bessi xəstələnir.
Sonrakı sətirin hər biri roller coaster-in bir hissəsini təsvir edir. Hər sətirdə iki tam ədəd verilir:
F D
Burada (1 \leq F \leq 20) bu hissədə Bessi gözlərini açıq tutarsa ümumi əyləncəyə əlavə olunacaq miqdardır, (1 \leq D \leq 500) isə gözləri açıq tutarsa başgicəllənmədə artımdır. Hissələr ardıcıllıqla verilir. Girişdə üç olan sətir olduqda giriş bitmiş sayılır.
Hər bir test üçün Bessinin başgicəllənmə həddini keçmədən əldə edə biləcəyi maksimum əyləncə səviyyəsini göstərən bir tam ədəd çap edin. Hər tam ədədi ayrıca sətirə, arada boşluq olmadan yazın. Cavablar arasında boş sətir qoymayın.
Nümunə 1