Bir dəfə Çində
Tezliklə "Çində Bir Gün" adlı yeni kompüter oyunu işıq üzü görəcək. Hələlik isə demo versiyası ilə kifayətlənməliyik. Oyun belədir: bir cigit kung-fu sənətini öyrənir və müxtəlif bandit yuvalarını gəzərək orada pis oğlanları döyür və onların talan etdiyi pulları ələ keçirir. Kung-fu bacarığı müəyyən bir qeyri-mənfi tam ədədlə ifadə olunur.
Oyunda ümumilikdə N bandit yuvası var. i-ci yuva üç göstəriciyə malikdir: Q_i, S_i və M_i. Q_i rəqəmi cigitin kung-fu bacarığının i-ci yuvada banditləri talan edə bilməsi üçün minimal səviyyəsini göstərir. Əgər onun kung-fu bacarığı Q_i-dən azdırsa, ora girməməsi daha yaxşıdır. S_i isə cigitin i-ci yuvadan ala biləcəyi məbləği (yuanla) göstərir, əgər onun kung-fu bacarığı Q_i-yə bərabərdirsə.
Əgər onun kung-fu bacarığı daha yaxşıdırsa, o, banditlərdən daha çox pul ala bilər. Daha dəqiq desək, əgər kung-fu bacarığı (onu K ilə işarə edək) Q_i ilə Q_i·M_i arasında (hər iki hədd daxil olmaqla) yerləşirsə, cigit banditlərdən S_i·(K/Q_i) məbləğini alacaq. Əgər kung-fu bacarığı Q_i·M_i-dən çoxdursa, cigit dəqiq S_i·M_i məbləğini alacaq, çünki oradan daha çox almaq mümkün deyil.
Hər şey sadə görünür, amma bir çətinlik var. Cigit kung-fu sənətini ustad Zen-dən öyrənməlidir və hər təlim saatı üçün 1 yuan ödəməlidir. Məlum olduğu kimi, tələbənin səviyyəsi nə qədər yüksəkdirsə, onun bacarığını artırmaq üçün bir o qədər çox məşğul olmalıdır. Səviyyəni X_1-dən X_2-yə qaldırmaq üçün oğlanın A·(X_2^2-X_1^2) saat məşğul olması lazımdır.
Ustad Zen yalnız tam saatlarla təlim keçirir. O, kreditlə də öyrədə bilər ki, cigit bacarıqlarını tətbiq etdikdən sonra ona pulu qaytarsın.
Oyunun əvvəlində cigit kung-fu bacarığına malik deyil (yəni onun səviyyəsi 0-dır) və balansı sıfırdır. Banditlərdən alınan pullarla təlim üçün xərclənən məbləğ arasındakı fərqi, yəni maksimum mümkün mənfəəti tapın.
Giriş verilənləri
Birinci sətir N (1 ≤ N ≤ 10000) və A (0 ≤ A ≤ 10, rəqəm ən çox 3 ondalık dəqiqliklə verilmişdir) ədədlərini ehtiva edir.
Növbəti N sətirin hər biri Q_i, S_i və M_i (1 ≤ Q_i, S_i ≤ 1000, 1 ≤ M_i ≤ 10. M_i, S_i və Q_i tam ədədlərdir) ədədlərini ehtiva edir.
Çıxış verilənləri
Bir ədəd - cigitin maksimum mənfəəti. Cavabınız doğru cavabdan 0.000001 (1e-6) fərqlənməməlidir.