선거 유세 동선

선거철 유세의 핵심은 여러 장소를 돌며 준비한 연설을 하고, 최대한 많은 잠재 유권자의 마음을 얻는 것입니다. 하지만 하루에 쓸 수 있는 시간은 한정되어 있어 모든 곳을 갈 수는 없습니다. 그래서 이동 시간, 각 장소에서 머무는 시간, 그리고 얻을 수 있는 유권자 수를 잘 저울질하여 유세 동선을 신중히 계획해야 합니다. 이런 계획은 컴퓨터에게 맡기는 편이 낫습니다.

각 유세 후보지마다 그곳에 들렀을 때 얻을 것으로 기대되는 유권자 수와, 그곳에서 머물러야 하는 시간이 주어집니다. 또한 임의의 두 장소(순서가 있는 쌍)에 대해 한 곳에서 다른 곳으로 이동하는 데 걸리는 시간이 주어집니다. 사용할 수 있는 전체 시간이 주어지면, 얻는 유권자 수를 최대로 만드는 동선을 계획할 수 있습니다.

유세는 항상 1번 도시에서 출발하여 다시 1번 도시로 돌아와야 합니다. 다만 1번 도시에서 반드시 유세를 해야 하는 것은 아니며, 그곳에 머무는 시간을 쓰지 않고 지나칠 수 있습니다. 마찬가지로 다른 도시도 유세를 하지 않고 경유만 할 수 있으며, 이때는 그 도시에서 머무는 시간이 들지 않고 유권자도 얻지 않습니다.

첫째 줄에는 파일에 담긴 데이터 집합의 개수 $K \ge 1$이 주어집니다. 이어서 아래 형식의 데이터 집합이 $K$개 주어집니다.

각 데이터 집합의 첫 줄에는 두 수 $n$과 $H$가 주어집니다. 여기서 $1 \le n \le 10$은 유세 후보지의 수이고, $1.0 \le H \le 24.0$은 사용할 수 있는 전체 시간입니다(소수일 수 있습니다).

그다음 $n$개의 줄에는 각 유세 후보지가 한 줄씩 설명됩니다. 각 줄에는 정수 $v_i \ge 0$과 소수 $h_i \ge 0$, 두 수가 주어집니다. $v_i$는 그 장소에서 얻을 수 있는 유권자 수이고, $h_i$는 그곳에서 머물러야 하는 시간입니다.

마지막으로 $n$개의 줄이 더 주어지며, 각 줄에는 $n$개의 수가 있습니다. $i$번째 줄의 $j$번째 수는 도시 $i$에서 도시 $j$로 이동하는 데 걸리는 시간(소수)입니다. 따라서 $i$번째 줄의 $i$번째 수는 $0$이지만, 도시 $i$에서 도시 $j$로 가는 시간과 도시 $j$에서 도시 $i$로 가는 시간이 반드시 같지는 않습니다.

각 데이터 집합마다 먼저 한 줄에 “Data Set x:”를 출력합니다. 여기서 $x$는 데이터 집합의 번호입니다. 그다음 줄에 주어진 시간 $H$ 안에 얻을 수 있는 유권자 수의 최댓값을 출력합니다. 동선은 항상 1번 도시에서 시작하여 1번 도시로 돌아오며, 1번 도시에서 반드시 유세를 할 필요는 없습니다.