고르바초프 서기장님, 이 장벽을 허무십시오!

동독과 서독이 통일하던 시기의 상징적인 장면 하나는 동베를린과 서베를린을 가르던 장벽을 허무는 모습이었다. 그 장벽에서 떼어낸 벽돌 조각은 지금 여러 박물관과 개인 소장품에 남아 있다. 관광객에게 비싼 값으로 팔린 조각 중에는 정말 장벽에 있던 벽돌인지 확인할 수 없는 것도 많다.

1987년 레이건 대통령은 소련에 동독을 서방으로 개방하라고 요구하면서 "Mr. Gorbachev, tear down this wall!"이라고 말했다. 장벽은 길고 튼튼했으니 고르바초프 혼자 허물었다면 시간이 아주 오래 걸렸을 것이고, 아마 사람을 몇 명 더 불렀을 것이다. 여러 사람이 함께 장벽을 전부 허무는 데 걸리는 시간을 구하라.

장벽은 2차원 좌표평면 위의 점을 순서대로 나열해서 주어진다. 좌표는 모두 정수이고, 장벽의 각 구간은 수평이거나 수직이며 비스듬한 구간은 없다. 한 사람이 장벽 1미터를 허무는 데 걸리는 시간과 일하는 사람 수도 함께 주어진다.

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

각 데이터 집합의 첫 줄에는 정수 $n$, $s$, $p$가 주어진다. $1 \le n \le 1000$은 장벽을 이루는 선분의 개수, $0 < s < 100$은 한 사람이 장벽 1미터를 허무는 데 걸리는 시간, $1 \le p \le 1000$은 장벽을 허무는 사람 수다.

다음 $n + 1$개의 줄에는 각각 두 정수 $x_i$, $y_i$가 주어진다($-10000 \le x_i, y_i \le 10000$). 이는 장벽을 이루는 $i$번째 점이고, 장벽의 $i$번째 선분은 $(x_i, y_i)$에서 $(x_{i+1}, y_{i+1})$까지 이어진다. 모든 구간은 수평이거나 수직이므로 각 $i$에 대해 $x_{i+1} = x_i$이거나 $y_{i+1} = y_i$다. 또한 장벽은 자기 자신과 교차하지 않는다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. x는 1부터 세는 데이터 집합의 번호다.

다음 줄에 $p$명이 장벽 전체를 허무는 데 걸리는 시간을 출력한다. 시간은 정수로 올림한다. 예를 들어 3.1시간이 걸리면 3이 아니라 4를 출력한다.

각 데이터 집합 뒤에 빈 줄을 하나 출력한다.