B. Blood Memories
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Panda is playing a game, in which he is fighting the Demon's army with a party of $$$n$$$ characters, numbered $$$1$$$ to $$$n$$$. Each round begins with $$$m$$$ Ap (energy points) available to the party.

Each character $$$i$$$ has a skill that deals $$$a_i$$$ damage and normally costs $$$c_i$$$ Ap. In any round, each character can choose to either use their skill once or do nothing with zero cost. The total Ap cost of all skills used in a round must not be more than $$$m$$$. Any remaining Ap at the end of the round is discarded, and the party is fully refreshed with $$$m$$$ Ap for the next round.

Due to the unique mechanics of this game, if a character uses their skill in a round, its Ap cost for the next round becomes $$$c_i + k$$$. If the character continues using the skill in consecutive rounds, the cost stays at $$$c_i + k$$$ (it does not increase further). If a character does not use their skill in a round, the skill cost will reset to $$$c_i$$$ for the very next round.

Panda wants to maximize the total damage dealt over a total of $$$R$$$ rounds. Find the maximum possible total damage.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$), denoting the number of test cases.

For each test case, the first line contains four integers $$$n,m,k,R$$$ ($$$1\le n\le 6$$$, $$$1\le m,k\le 10^3$$$, $$$1\le R\le 10^9$$$). $$$n$$$ is the number of characters in the party, $$$m$$$ is the Ap gained at the start of each round, $$$k$$$ the temporary Ap cost increase when a skill is used, and $$$R$$$ is the total number of rounds.

For the next $$$n$$$ lines, each line contains two integers $$$a_i, c_i$$$ ($$$1\le a_i\le 10^6$$$, $$$1\le c_i\le m$$$), which are the damage and initial Ap cost for character $$$i$$$.

Output

Output a single integer, denoting the maximum total damage that can be achieved.

Example
Input
3
3 7 1 5
59 3
13 2
81 4
5 14 2 9
66 8
20 2
25 4
39 6
57 7
4 13 7 16
18 2
13 5
33 4
7 1
Output
490
939
741