Համլետը և բարակաբլիթները
Մոտենում է նոր տարին և մայրիկները պետք է բարակաբլիթներ (բլինչիկ) պատրաստեն։ Համլետը իր մայրիկին օգնելու համար բարակաբլիթ թխող ռոբոտներ է պատրաստել։ Ռոբոտի երկու ձեռքերից յուրաքանչյուրը ժամանակի յուրաքանչյուր պահին կարող է կատարել հետևյալ գործողություններից մեկը՝ խմորը շերեփով լցնել թավայի մեջ, շրջել բարակաբլիթը, հանել բարակաբլիթը։ Ռոբոտները մի փոքր թերություն ունեն՝ առաջին գործողության ժամանակ շերեփում կարող է տարբեր քանակությամբ խմոր լինել և բարակաբլիթների թխելու ժամանակները տարբեր են ստացվում (դա այլ հանգամանքներից էլ է կախված)։
Առաջին փորձերը պսակվեցին հաջողությամբ, և հիմա Համլետը բարակաբլիթներ համտեսելու արագ սնննդի կետ է բացել։ Հենց հաճախորդներին սպասարկողը մոտենում է խոհանոցի պատուհանին և ասում է պայմանական կոդը՝ ԲԲ, հերթական՝ ազատ ձեռք ունեցող, խոհարար ռոբոտը նույն վայրկյանին պետք է կատարի առաջին գործողությունը։ Հենց որևէ բարակբլիթի մի կողմը թխվում է, նույն վայրկյանին այն պետք է շուռ տալ։ Երկրորդ կողմը թխվելուն պես պետք է հանել։
Ենթադրենք հայտնի են յուրաքանչյուր բարակաբլիթի առաջին գործողությունը կատարելու պահերը և մի կողմը թխվելու ժամանակը։ Առնվազն քանի՞ խոհարար-ռոբոտ է պետք, որպեսզի ոչ մի բարակաբլիթ չփչանա և բոլոր պատվերները կատարվեն։
Մուտքային տվյալներ
Առաջին տողում տրված է բարակաբլիթների պատվերների
n (1 ≤ n < 1000) քանակը։ Հաջորդ n տողերից յուրաքանչյուրում տրված են երկուական թվեր, առաջին թիվը ցույց է տալիս խմորը թավայի մեջ լցնելու Ti (1 ≤ Ti ≤ 1000) պահը, երկրորդ թիվը՝ տվյալ բարակաբլիթի մի կողմը թխելու Di տևողությունը (1 ≤ Di ≤ 1000)։ Ենթադրում ենք, որ երկու կողմերն էլ թխվում են նույն ժամանակում։Ելքային տվյալներ
Պետք է արտածել ճիշտ մեկ բնական թիվ՝ ռոբոտների անհրաժեշտ նվազագույն քանակը։
Օրինակներ
Մուտք. | Ելք. |
3
1 5
1 5
1 5 | 2 |
3
1 3
5 1
2 2 | 1 |
Բացատրություն
Առաջին օրինակում երկու ձեռքը չի բավականացնի միաժամանակ երեք միատեսակ բարակաբլիթ պատրաստելու համար։ Պետք է երկու ռոբոտ։
Երկրորդ օրինակում մեկ ռոբոտը բավական է։ Ռոբոտի գործողություններն ըստ վայրկյանների.
- լցնում է առաջին բարակաբլիթի խմորը
- լցնում է երրորդ բարակաբլիթի խմորը
- գործ չունի անելու
- մի ձեռքով շրջում է առաջին, մյուսով՝ երրորդ բարակաբլիթը։
- լցնում է երկրորդ բարակաբլիթի խմորը
- մի ձեռքով շրջում է երկրորդ բարակաբլիթը, մյուսով հանում է երրորդը։
- մի ձեռքով հանում է առաջին, մյուսով՝ երկրորդ բարակաբլիթը։
Աղբյուրը. Դպրոցական 2020
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB