화폐 통일

두 나라를 하나로 합칠 때 반드시 해야 하는 일 중 하나가 화폐 통일이다. 투기를 막으려면 교환 비율을 미리 고정해 두는 편이 낫다. 원칙대로라면 모두가 옛 화폐를 최대한 빨리 새 화폐로 바꿔서 물건을 사려 할 것이다. 실제로는 그렇지 않다. 통일이 끝까지 갈지 믿지 못하는 사람도 있고, 그저 옛 화폐가 아까워서 조금 더 쥐고 있으려는 사람도 있다. 더 이상 찍지 않는 화폐의 가치가 오르기를 기대하는 사람도 있는데, 수십 년을 기다릴 생각이 아니라면 그 기대는 이루어지지 않는다.

당신은 1일이 시작될 때 옛 화폐 $m$단위를 가지고 있다. 앞으로 $p$번 물건을 사는데, $i$번째 구매는 $d_i$일에 일어나고 $v_i$단위가 필요하다. 이는 $d_i$일까지(그날 포함) 아직 내놓지 않은 옛 화폐 $v_i$단위를 은행에서 바꿔 두어야 한다는 뜻이다. 은행에 한 번 갈 때마다 수고 $t$가 들고, 갈 수 있는 횟수는 최대 $b$번이다. 한 번에 바꾸는 금액에는 상한이 없고, 은행에 가는 날도 자유롭게 고른다.

향수 값은 하루에 옛 화폐 1단위당 $n$이다. 옛 화폐 1단위는 1일부터 그것을 은행에 내놓은 날까지(그날 포함) 매일 $n$을 준다. 끝까지 바꾸지 않은 돈은 시간이 멈출 때까지 매일 $n$을 준다. 시간은 마지막 구매가 있는 날이 끝나는 순간 멈춘다.

향수 값의 합에서 수고의 합을 뺀 값을 최대로 하라.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. $K \ge 1$이다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 음이 아닌 정수 다섯 개 $m$, $p$, $t$, $n$, $b$가 주어진다. $m \le 1000$은 1일이 시작될 때 가진 돈이다. $1 \le p \le 200$은 구매 횟수다. $t \le 1000$은 은행에 한 번 가는 데 드는 수고다. $n \le 100$은 하루에 옛 화폐 1단위당 얻는 향수 값이고, 수고와 같은 단위로 잰다. $1 \le b \le p$는 은행에 갈 수 있는 최대 횟수다.

다음 $p$개의 줄에 구매가 하나씩 주어진다. 각 줄에는 양의 정수 $d$와 $v$가 있다. $d \le 10000$은 구매가 일어나는 날이고, $v$는 필요한 금액이다. 같은 날에 두 번 구매하는 일은 없고, 구매는 $d$가 증가하는 순서로 주어진다. 모든 구매를 감당할 돈은 항상 충분하다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 x는 데이터 집합의 번호다. 다음 줄에 얻을 수 있는 향수 값의 합에서 수고를 뺀 최댓값을 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.