베니스의 상인

셰익스피어의 희곡 「베니스의 상인」에는 샤일록이라는 유대인 고리대금업자가 나온다. 그는 기독교인들에게, 그중에서도 표제의 상인 안토니오에게 여러 방식으로 여러 번 상처를 받았다. 안토니오의 친구 바사니오가 사랑하는 여인에게 구혼하려고 3000두카트를 급히 빌려야 했을 때, 안토니오의 돈은 무역 선단에 모두 묶여 있었다. 그래서 안토니오는 기한까지 3000두카트를 갚지 못하면 자기 살 1파운드를 내주겠다는 계약서에 샤일록과 함께 서명한다. 폭풍으로 선단을 잃으면서 이야기는 험악해진다.

여기서는 안토니오가 미리 했어야 할 위험 분석, 즉 배가 저마다 돌아올 확률이 얼마이고 기한까지 돈을 갚지 못할 확률이 얼마인지는 다루지 않는다. 대신 계약 시점에 배들이 어디에 있느냐에 따라 안토니오가 정해진 날짜까지 샤일록에게 갚을 수 있는 금액이 얼마인지만 계산한다.

기한까지 남은 날수와 배의 속력이 주어지고, 배마다 베네치아에서 떨어진 거리와 실은 화물의 가치가 두카트 단위로 주어진다. 안토니오가 기한까지 갚을 수 있는 두카트를 출력하라.

첫 줄에 파일에 들어 있는 데이터 세트의 수 $K \ge 1$이 주어진다. 이어서 $K$개의 데이터 세트가 다음 형식으로 주어진다.

데이터 세트의 첫 줄에는 정수 $n$, $s$, $d$가 주어진다. $0 \le n \le 200$은 안토니오가 가진 배의 수, $1 \le s \le 100$은 배가 하루에 나아가는 거리(마일), $1 \le d \le 365$는 계약 기한까지 남은 날수다.

다음 $n$개의 줄에는 각각 정수 $d_i$, $v_i$가 주어진다. $0 \le d_i \le 10000$은 $i$번 배가 베네치아에서 떨어진 거리(마일), $0 \le v_i \le 100000$은 $i$번 배가 실은 화물의 가치다.

각 데이터 세트마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 그 데이터 세트의 번호다. 그 다음 줄에 안토니오가 $d$일 뒤에 샤일록에게 갚을 수 있는 두카트의 총합을 출력한다. 배가 $d$일째에 정확히 도착하면 그 화물도 상환에 쓸 수 있다고 본다.

각 데이터 세트 뒤에는 빈 줄을 하나 출력한다.