WKY's Training Challenge

Teacher Lao Wang is impressed by WKY's programming skills and decides to train him using a unique method. In this challenge, WKY is given a set of problems, each associated with a knowledge point. For each knowledge point \(i\), the teacher takes a fixed time \(t_i\) to solve any problem of that type. WKY's time to solve a problem of knowledge point \(i\) is computed as:

\(\text{Time} = t_i \times \frac{\text{teacher's skill}}{\text{WKY's skill}}\)

Given a total allowed time \(T\), WKY must choose a subset of problems to maximize his total reward. Note that problems sharing the same knowledge point have the same time cost for WKY and that the reward for each problem is independent of its knowledge point.

inputFormat

The input is as follows:

• The first line contains three integers: \(s_w\) (WKY's skill), \(s_t\) (teacher's skill) and \(T\) (allowed time).
• The second line contains an integer \(m\), the number of knowledge points.
• The third line contains \(m\) space-separated integers: \(t_1, t_2, \ldots, t_m\), where \(t_i\) is the teacher's time to solve a problem of knowledge point \(i\).
• The fourth line contains an integer \(n\), the number of problems.
• Each of the next \(n\) lines contains two integers: \(k\) (the 1-indexed knowledge point ID) and \(r\) (the reward for that problem).

Assume that the teacher's skill is always an integer multiple of WKY's skill so that the ratio \(\frac{s_t}{s_w}\) is an integer.

outputFormat

Output a single integer representing the maximum total reward WKY can obtain within the allowed time \(T\).

sample

1 2 10
3
3 2 5
4
1 10
2 5
2 8
3 15

15