«Քաջ Նազար»
«Քաջ Նազար» ձեռնարկությունը մատուցում է բնակարաններում ճանճեր, միջատներ վերացնելու ծառայություն։ Գովազդի արդյունքում ձեռնարկությունը ստացել է
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