Problem C
Koffínhraði
Languages
en
is
Oh no! Now towards the end of the term there are all kinds of exams and final projects closing in! By your side you of course have your trusty stash of caffeinated drinks. Tea, coffee, energy drinks and more can help you cover all the material and finish all the projects in the time you have. Such drinks are however far from free, so now the question is how deep you have to dip into your stash to get everything done in time.
Each drink halves the number of hours a task will take, rounded down to the nearest whole number of hours. Two drinks will thus half the hours in this manner twice. For example a $7$ hour project goes down to a single hour after two drinks.
Each exam or project has a deadline and has to be finished by that date. Everything is given in hours and we of course assume there will be no sleep or other distractions from working on studies.
Input
The first line of input contains a single positive integer $n$, the number of tasks. Next there are $n$ lines, each containing two integers $1 \leq t_ i, s_ i \leq 10^9$. $t_ i$ denotes the number of hours it will take to complete the task without caffeine, $s_ i$ denotes how many hours from now the task has to be finished.
Output
Print the minimum number of caffeinated drinks it will take to finish everything in time. You may assume that all tasks can be finished in time given enough caffeine. Note that this is not true to real life.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$n = 1$ |
|
2 |
20 |
All $t_ i = 1$ and $n \leq 10^5$. |
|
3 |
20 |
All $s_ i = 2016$ ($12$ weeks) and $n \leq 10^5$. |
|
4 |
20 |
$n \leq 500$. |
|
5 |
20 |
$n \leq 10^5$. |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 5 10 8 10 10 21 15 21 |
3 |
