Description

His teacher Lao Wang is amazed by his programming skills and decides to train this kid.

Lao Wang’s training method is unusual: he makes WKY solve many problems in one go and requires him to finish within a specified time. To raise his own prestige, Lao Wang also solves all these problems himself.

WKY and Lao Wang each have a skill value. The ratio of their skill values is inversely proportional to the ratio of the time they need to solve the same problem. For example, if WKY’s skill value is $1$ and Lao Wang’s skill value is $2$, then the time WKY needs to solve the same problem is $2$ times Lao Wang’s time.

Each problem belongs to a “knowledge point” such as recursion, dynamic programming, shortest paths, or network flow. Here we do not consider the semantics of these topics; we only label them as knowledge point $1$, knowledge point $2$, and so on. Each knowledge point has its own difficulty.

For WKY, all problems under the same knowledge point take the same amount of time. Each problem has a unique reward value assigned by Lao Wang, and this reward has no necessary connection with the problem’s knowledge point.

Now WKY asks you to help compute the maximum total reward he can obtain within the time specified by Lao Wang.

Input Format

The input contains the following:

• First line: WKY’s skill value and Lao Wang’s skill value. It is guaranteed that WKY’s skill value is less than Lao Wang’s (even if that seems unrealistic), and Lao Wang’s skill value is an integer multiple of WKY’s skill value.
• Second line: the total number of problems $m$ and the total number of knowledge points $n$.
• Third line: $n$ integers. The $i$-th integer is the time Lao Wang needs to solve one problem whose knowledge point is $i$.
• Next $m$ lines: each line contains two integers $p$, $q$. Here $p$ is the problem’s knowledge point, and $q$ is its reward value.
• Last line: the specified total time limit.

Output Format

Output one line with the maximum total reward WKY can obtain.

1 2
6 4
1 2 3 4
1 5
2 6
3 3
4 8
3 3
4 5
20

22

Hint

Constraints:

• For $100\%$ of the testdata: $1 \leq n, m \leq 100$, time limit $\leq 5000$. $1 \leq p \leq n$, $1 \leq q \leq 1000$.

Translated by ChatGPT 5