Ալգորիթմներ և Տվյալների Կառուցվածքներ

Առաջադրանքներ և վերջնաժամկետներ

Տրված են 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

Բացատրություն

  1. 10 + 3 + 7

    1. Նախ կատարում ենք 1 վերջնաժամկետ ունեցող առաջադրանքը ⇒ ստանում ենք 3

    2. Այնուհետև կատարում ենք 2 վերջնաժամկետ ունեցող առաջադրանքը ⇒ ստանում ենք 7

    3. Վերջում կատարում ենք 4 վերջնաժամկետ ունեցող առաջադրանքը ⇒ ստանում ենք 10

  2. 100 + 200 + 300 + 200 (կատարում ենք միայն deadline=4 ունեցող առաջադրանքները)

    1. Կատարում ենք առաջադրանքը, որի շահույթը 100 է

    2. Կատարում ենք առաջադրանքը, որի շահույթը 200 է

    3. Կատարում ենք առաջադրանքը, որի շահույթը 300 է

    4. Կատարում ենք առաջադրանքը, որի շահույթը 200 է

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue