Problem D
Interview Preparation
With the internship season coming up, Johnny has began to prepare for the dreaded technical interviews. Johnny has upcoming interviews with $C$ different companies. The $i^\textrm {th}$ company will make Johnny an offer if and only if his technical skill is at least $a_ i$ and business skill is at least $b_ i$. Furthermore, Johnny knows that his current technical skill is $A$ and his current business skill is $B$, and that it takes him $t_ a$ minutes to increase his technical skill by $1$ and $t_ b$ minutes to increase his business skill by $1$ (skill level increase is continuous and linear).
Johnny has $T$ minutes to prepare for the interviews. How many offers could he receive at most, assuming he prepares optimally?
Input
The first line of the input contains five integers $A, B, T, t_ a, t_ b$, where $0\leq A, B\leq 100\, 000$, $1\leq t_ a, t_ b\leq 10$, and $0\leq T\leq 10^9$.
The next line contains a single integer $C$, $1\leq C\leq 150\, 000$.
The next $C$ lines each contains a pair of integers $a_ i$ and $b_ i$, $0\leq a_ i, b_ i\leq 10^9$.
Output
Output a single integer denoting the largest number of offers Johnny will receive assuming he prepares optimally.
Sample Input 1 | Sample Output 1 |
---|---|
1 1 7 2 1 3 4 2 2 3 1 5 |
2 |