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?


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 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
4 2
2 3
1 5

Please log in to submit a solution to this problem

Log in