자전거 공유 서비스

샤름엘셰이크시가 자전거 공유 서비스를 시작한다. 도시의 요지에 대여소를 $N$개 세우고, 모든 대여소에 같은 용량 $C$를 준다. 용량이 $C$인 대여소에서는 아침에 최대 $C$명이 자전거를 가져가고, 저녁에 최대 $C$명이 자전거를 반납한다. 두 제한은 서로 독립이다. 아침에 아무도 자전거를 가져가지 않은 대여소도 저녁에는 자전거를 $C$대까지 받는다.

당신은 이 서비스의 기획팀에서 수익성을 확인하려고 시장 조사를 했고 다음을 알아냈다. 서비스를 쓰려는 집단이 정확히 $M$개 있다. 한 집단은 $P$명으로 이루어지고, 같은 집단에 속한 사람은 모두 똑같이 움직인다. 아침에 대여소 $St$에서 자전거를 가져가고 저녁에 대여소 $En$에 반납하며, 그 대가로 한 사람이 정확히 $X$를 낸다. 출발 대여소와 도착 대여소가 같을 수도 있다. 자전거 한 대는 하루 종일 한 사람이 쓰므로 여러 사람이 나눠 쓰지 못한다.

대여소의 자전거가 이용을 원하는 사람을 다 감당하지 못할 수도 있다. 그러면 받는 금액의 합이 가장 커지도록 이용자를 골라도 된다. 한 집단을 통째로 받을 필요는 없고 같은 집단에서 일부만 골라도 된다.

용량을 크게 잡을수록 비용이 든다. 용량이 $C$일 때 드는 비용은 $D \times C$다. 용량 $C$는 0 이상의 정수 중에서 마음대로 고르며 0도 된다. 총수입에서 총비용을 뺀 이익의 최댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 50$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 세 개 $N$, $M$, $D$ ($1 \le N \le 50$, $1 \le M \le 250$, $1 \le D \le 100000$)가 공백 하나로 구분되어 주어진다. 차례대로 대여소의 수, 집단의 수, 용량 1당 드는 비용이다.

이어서 $M$개의 줄에 정수 네 개 $P$, $St$, $En$, $X$ ($1 \le P \le 100000$, $1 \le St, En \le N$, $1 \le X \le 100000$)가 주어진다. 차례대로 집단의 인원수, 출발 대여소, 도착 대여소, 한 사람이 내는 금액이다.

각 테스트 케이스마다 한 줄에 Case n:을 출력하고, 공백 하나를 둔 다음 최대 이익을 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호다.