MP3 Pleyer
Georgun yeni MP3 pleyerinin bir çox maraqlı xüsusiyyətləri var, onlardan biri də düymə kilididir. Əgər heç bir düymə T saniyə ərzində basılmazsa, bütün düymələr kilidlənir. Kilid aktiv olduqda, düymələr öz funksiyalarını yerinə yetirmir, lakin hər hansı bir düymə basıldıqda kilid açılır.
Məsələn, T = 5 olduğunu və pleyerin hazırda kilidli olduğunu fərz edin. Georg A düyməsini basır, 3 saniyə gözləyir, B düyməsini basır, 5 saniyə gözləyir, C düyməsini basır, 6 saniyə gözləyir və D düyməsini basır. Bu halda yalnız B və C düymələri öz adi funksiyalarını yerinə yetirir. Qeyd edək ki, düymələr C və D düymələri arasında kilidlənmişdir.
MP3 pleyerin səs səviyyəsi + və - düymələri ilə idarə olunur, müvafiq olaraq səs səviyyəsini 1 vahid artırır və azaldır. Səs səviyyəsi 0 ilə V_max arasında tam ədəddir. V_max səs səviyyəsində + düyməsini basmaq və ya 0 səs səviyyəsində - düyməsini basmaq səs səviyyəsini dəyişməz saxlayır.
Georg T dəyərini bilmir. O, bunu bir təcrübə ilə tapmaq istədi. Kilidli klaviatura ilə başlayaraq, N + və - düymələri sırasını basdı. Təcrübənin sonunda Georg pleyerin ekranından son səs səviyyəsini oxudu. Təəssüf ki, ilk düyməni basmadan əvvəl səs səviyyəsini qeyd etməyi unutdu. Bu tapşırıq üçün naməlum ilkin səs səviyyəsi V_1 və məlum son səs səviyyəsi V_2 ilə göstəriləcək.
Sizə V_2 dəyəri və Georgun onları basdığı ardıcıllıqla düymə basmaları siyahısı verilir. Hər bir düymə üçün, düymənin növü (+ və ya -) və təcrübənin başlanğıcından düymənin basıldığı ana qədər olan saniyələrin sayı verilir. Tapşırıq təcrübənin nəticəsi ilə uyğun olan T dəyərinin ən böyük mümkün tam ədədini tapmaqdır.
Giriş verilənləri
Girişin ilk sətri üç boşluqla ayrılmış tam ədəd N, V_max və V_2 (0 ≤ V_2 ≤ V_max) ehtiva edir. Növbəti N sətrin hər biri ardıcıllıqla bir düymənin təsvirini ehtiva edir: bir simvol + və ya -, bir boşluq və bir tam ədəd C_i (0 ≤ C_i ≤ 2·10^9), təcrübənin başlanğıcından olan saniyələrin sayı. Sizə verilmişdir ki, düymə basmaları sıralanmış qaydada və bütün vaxtlar fərqlidir (yəni, C_i < C_{i+1} üçün bütün 1 ≤ i < N).
Məhdudiyyətlər
Siz 2 ≤ N ≤ 100000 və 2 ≤ V_max ≤ 5000 olduğunu fərz edə bilərsiniz.
40 xal dəyərində olan test hallarında N ≤ 4000.
70 xal dəyərində olan test hallarında N·V_max ≤ 400000.
Çıxış verilənləri
Əgər T istənilən qədər böyük ola bilərsə, bir sətirdə "sonsuzluq" sözünü çıxış edin (aydınlıq üçün dırnaq işarələri).
Əks halda, bir sətirdə iki tam ədəd T və V_1 bir boşluqla ayrılmış şəkildə çıxış edin.
Dəyərlər belə olmalıdır ki, kilidləmə vaxtı T ilə təcrübəni həyata keçirmək və V_1 səs səviyyəsindən başlayaraq V_2 son səs səviyyəsini versin. Əgər bir neçə mümkün cavab varsa, ən böyük T ilə olanı çıxış edin; əgər hələ də bir neçə mümkün cavab varsa, ən böyük V_1 ilə olanı çıxış edin.
(Qeyd edək ki, ən azı bir həll həmişə mövcuddur: T = 0 üçün heç bir düymə öz hərəkətini yerinə yetirmir, beləliklə V_1 = V_2 götürmək kifayətdir.)