Առաջադրանքներ և վերջնաժամկետներ
Տրված են
n առաջադրանքներ, որոնցից յուրաքանչյուրն ունի վերջնաժամկետ և որոշակի գումար, որը կստանաք, եթե այն ավարտեք մինչև վերջնաժամկետը։ Յուրաքանչյուր առաջադրանքը կատարելու համար անհրաժեշտ է 1 օր։ Եթե առաջադրանքը վերջնաժամկետից ուշ հանձնեք, գումարը չեք ստանա։Սկսում եք օր 1-ից։ Որքա՞ն գումար կարող եք աշխատել։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ), որը առաջադրանքների քանակն է։Հաջորդ
n տողերում տրված են բացատով բաժանված ամբողջ թվեր (1 ≤ , ≤ )․ այստեղ -ն առաջադրանքի վերջնաժամկետն է, իսկ -ն՝ գումարը, որ կստանաք այն ժամանակին ավարտելու դեպքում։Ելք
Ծրագիրը պետք է տպի առավելագույն ընդհանուր գումարը, որը կարող եք աշխատել։
Օրինակներ
Մուտք | Ելք |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Բացատրություն
- 10 + 3 + 7
- Նախ կատարում ենք 1 վերջնաժամկետ ունեցող առաջադրանքը ⇒ ստանում ենք 3
- Այնուհետև կատարում ենք 2 վերջնաժամկետ ունեցող առաջադրանքը ⇒ ստանում ենք 7
- Վերջում կատարում ենք 4 վերջնաժամկետ ունեցող առաջադրանքը ⇒ ստանում ենք 10
- 100 + 200 + 300 + 200 (կատարում ենք միայն deadline=4 ունեցող առաջադրանքները)
- Կատարում ենք առաջադրանքը, որի շահույթը 100 է
- Կատարում ենք առաջադրանքը, որի շահույթը 200 է
- Կատարում ենք առաջադրանքը, որի շահույթը 300 է
- Կատարում ենք առաջադրանքը, որի շահույթը 200 է
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB