«Քաջ Նազար»

«Քաջ Նազար» ձեռնարկությունը մատուցում է բնակարաններում ճանճեր, միջատներ վերացնելու ծառայություն։ Գովազդի արդյունքում ձեռնարկությունը ստացել է N պատվեր։ Յուրաքանչյուր պատվեր ներկայացվում է մեկ թվազույգի միջոցով։ Առաջին թիվը ցույց է տալիս արժեքը, որը կախված է բնակարանի մեծությունից և տիպից։ Երկրորդ թիվը ցույց է տալիս, թե պատվիրատուն առավելագույնը քանի օր կարող է սպասել իր պատվերի կատարմանը։
Քանի որ միակ աշխատողը Ուստիանն է, ձեռնարկությունը կարող է օրական մեկ պատվեր կատարել։ Օգնեք Քաջ Նազարին՝ ձեռնարկության տնօրենին, ընտրել պատվերների այնպիսի ենթաբազմություն, որ ստացված գումարը լինի մաքսիմալ։ Կա ևս մեկ հանգամանք՝ Նազարը ցանկանում է M օր հետո փակել ձեռնարկությունը և գնալ հսկաների երկիրը։ Բայց աշխատանքները կարող են սկսել հենց գովազդ տալու օրը, որը պետք է համարել 0-րդ օր։

Մուտքային տվյալներ

Առաջին տողում տրված են երկու ամբողջ թվեր՝ պատվերների N և M ամբողջ թվերը (1 ≤ N ≤ 10 000, 1 ≤ M ≤ 100): Հաջորդ N տողերից յուրաքանչյուրում տրված են հերթական պատվերի ci արժեքը և այն կատարելու ti ժամկետը (1 ≤ ci ≤ 100 000, 0 ≤ ti ≤ M)։

Ելքային տվյալներ

Պետք է արտածել մեկ ամբողջ թիվ՝ առավելագույն գումարը, որ կարող է վաստակել «Քաջ Նազար» ձեռնարկությունը։

Օրինակ

Մուտք
Ելք
4 4 2000 1 3000 2 500 2 2200 0
7200
3 4 1500 1 2500 1 500 1
4000

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in