Currency Conversion

When two countries merge, one of the jobs is giving them a single currency. Fixing the conversion rate in advance keeps speculators away. In principle everybody then wants to exchange all their money as fast as possible and start buying with the new currency. In practice it does not go that way. Some people do not trust that the merger will go through, and some just like holding the old notes a little longer. A few also hope that a currency nobody prints any more will gain value, which will not happen unless they are willing to wait for decades.

You start the beginning of day 1 with $m$ units of the old currency. You will make $p$ purchases. Purchase $i$ happens on day $d_i$ and needs $v_i$ units, which means that on day $d_i$ or earlier you must have taken $v_i$ units of old money you have not given up before to the bank and exchanged them. Each trip to the bank costs $t$ effort, and you may go at most $b$ times. A single trip may exchange any amount, and you choose the days of your trips freely.

Nostalgia pays $n$ per day for each unit of old currency you still hold. One unit earns $n$ on every day from day 1 up to and including the day you hand it over at the bank. Money you never exchange earns $n$ every day until time ends. Time ends exactly at the end of the day of the last purchase.

Maximize the total nostalgia minus the total effort.

The first line contains the number of data sets $K$, with $K \ge 1$. It is followed by $K$ data sets of the form below.

The first line of a data set holds five non-negative integers $m$, $p$, $t$, $n$, $b$. $m \le 1000$ is the money you start out with at the beginning of day 1. $1 \le p \le 200$ is the number of purchases you make. $t \le 1000$ is the effort it takes to go to the bank once. $n \le 100$ is the nostalgia value you get per day per unit of money you hold that day, measured in the same units as the effort. $1 \le b \le p$ is the number of times you are allowed to go to the bank.

Then follow $p$ lines, one per purchase. Each line has two positive integers $d$ and $v$. The day $d \le 10000$ is when the purchase happens and $v$ is the amount of money it needs. No two purchases fall on the same day, and the purchases come in increasing order of $d$. There is always enough money for all purchases.

For each data set, first print Data Set x: on a line by itself, where x is the number of the data set. On the next line print the maximum total nostalgia minus effort you can accrue. Print a blank line after each data set.