Kvestlər

Dünya çempionatının ICPC finalında iştirak etməzdən əvvəl bir az dincəlmək üçün "Qüestlər" adlı kompüter oyununu oynamağa qərar verdiniz. Artıq bir neçə dəfə oynamısınız və indi mükəmməl bir keçid əldə etmək istəyirsiniz — finalın mükəmməl keçidinə hazırlaşmaq üçün!

Oyunda bir sıra qüestləri yerinə yetirmək lazımdır və hər birini tamamladıqda təcrübə xalları (XP) qazanırsınız. Qazandığınız ümumi təcrübə xalları sizin cari səviyyənizi müəyyən edir. Hər qazandığınız $v$ XP üçün yeni səviyyəyə keçirsiniz. Formal olaraq, hər hansı bir anda sizin səviyyəniz — ən azı $l\cdot v$ təcrübəniz olan ən böyük tam ədəddir.

Hər bir qüestə $x$ təcrübə miqdarı və hədəf çətinlik səviyyəsi $d$ təyin edilir. Əgər qüesti $d$ səviyyəsindən aşağı olmayan səviyyədə tamamlasanız, $x$ təcrübə qazanacaqsınız. Lakin, əgər qüesti $d$ səviyyəsindən aşağı səviyyədə tamamlasanız, $c\cdot x$ XP qazanacaqsınız. Konstanta $c$ — hədəf çətinlik səviyyəsi $d$-dən aşağı səviyyədə qüesti yerinə yetirdiyiniz zaman təcrübə bonusu verən çarpandır.

Siz bütün $n$ qüestləri və onlara uyğun $x$ və $d$ dəyərlərini bilirsiniz (Siz həmçinin $v$ və $c$ ədədlərini də bilirsiniz — bu oyunu çox oynamısınız). Siz həmçinin kifayət qədər təcrübəlisiniz ki, hər hansı bir qüesti, onun hədəf çətinlik səviyyəsindən və sizin səviyyənizdən asılı olmayaraq, yerinə yetirəsiniz. Siz bütün qüestləri elə bir ardıcıllıqla yerinə yetirmək istəyirsiniz ki, mümkün qədər çox təcrübə qazanasınız.

Giriş nümunəsində qazana biləcəyiniz maksimum təcrübə miqdarı $43$-dür, bu aşağıdakı şəkildə edilir. Əvvəlcə ikinci qüesti tamamlayın (səviyyəniz $0$ olduğuna görə və hədəf çətinlik səviyyəsi $2$ olan qüesti yerinə yetirdiyiniz üçün $4$ təcrübə qazanacaqsınız). Sonra birinci qüesti tamamlayın (hələ də səviyyəniz $0$ olduğuna görə və hədəf çətinlik səviyyəsi $1$ olduğuna görə $30$ təcrübə qazanacaqsınız). $34$ təcrübə ilə artıq səviyyə $3$-ə çatdınız. Nəhayət, üçüncü qüesti tamamlayın (artıq səviyyə $3$ olduğuna görə çarpansız $9$ təcrübə qazanacaqsınız).

Giriş verilənləri

Birinci sətirdə üç tam ədəd $n,v$ və $c$ verilir, burada $n(1\le n\le 2000)$ — oyundakı qüestlərin sayı, $v(1\le v\le 2000)$ — hər səviyyəyə çatmaq üçün lazım olan təcrübə miqdarı, və $c(2\le c\le 2000)$ — hədəf çətinlik səviyyəsinə çatmadan qüesti yerinə yetirdiyiniz zaman təcrübə çarpanı.

Daha sonra $n$ sətir gəlir, hər biri bir qüesti təsvir edən iki tam ədəd $x$ və $d$ ehtiva edir, burada $x(1\le x\le 2000)$ — hədəf çətinlik səviyyəsində və ya daha yüksək səviyyədə olduğunuz zaman bu qüesti yerinə yetirdiyiniz üçün qazandığınız təcrübə xalları, və $d(1\le d_i\le 10^6)$ — bu qüestin hədəf çətinlik səviyyəsidir.

Çıxış verilənləri

Bütün qüestləri yerinə yetirərək qazana biləcəyiniz maksimum təcrübə xallarının miqdarını çıxarın.

Nümunələr