아이스크림

실력에 비해 박봉에 시달리는 유명한 컴퓨터 과학자 몇 명이 고된 하루 일과를 마치고 집에 가는 길에 아이스크림을 먹기로 했다. 이들은 곧 한 스쿱당 가격이 트리플(세 스쿱) < 더블(두 스쿱) < 싱글(한 스쿱) 순으로 저렴하다는, 즉 더 큰 단위로 살수록 스쿱당 가격이 싸다는 사실을 알아차렸다. 하지만 모두가 세 스쿱을 원하는 것은 아니므로, 이들은 주문을 비용 효율적인 단위로 묶어서 산 뒤 스쿱을 서로 나누기로 했다. 예를 들어 세 사람이 각자 한 스쿱씩 원한다면, 트리플 하나를 주문해 세 개의 싱글 스쿱으로 나누어 모두를 가장 저렴하게 만족시킬 수 있다.

아이스크림 가게에는 바닐라와 초콜릿 두 가지 맛만 있다. 모두 콘 대신 컵을 사용하며, 컵은 필요한 만큼 무료로 받을 수 있다. 각 사람은 바닐라 몇 스쿱과 초콜릿 몇 스쿱을 원한다. 그런데 한 가지 문제가 있다. 하나의 주문 단위(싱글·더블·트리플) 안에 바닐라와 초콜릿이 각각 최소 한 스쿱씩 섞여 있으면, 아이스크림이 녹아 섞이면서 그 단위 안의 모든 스쿱이 오염된다. 예를 들어 맨 아래 초콜릿 위에 바닐라 두 개를 얹은 트리플은 세 스쿱 모두 오염된다. 두 맛을 모두 주문한 사람은 어차피 둘 다 원했으므로 오염을 신경 쓰지 않지만, 한 가지 맛만 주문한 사람은 이런 맛 오염을 절대 받아들이지 않는다. 모두의 주문을 만족시키는 최소 비용은 얼마인가?

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

각 데이터 집합의 첫 줄에는 네 정수 $n$, $s$, $d$, $t$가 주어진다. $n$은 컴퓨터 과학자의 수로 $1 \le n \le 100$이며, $s$, $d$, $t$는 각각 싱글·더블·트리플의 가격(센트)이다. 가격은 $1 \le s < d < t \le 1000$과 $s > \frac{1}{2}d > \frac{1}{3}t$를 만족한다. 이어서 $n$개의 줄에 각각 두 정수 $v$와 $c$가 주어진다. $v$는 그 손님이 원하는 바닐라 스쿱 수, $c$는 초콜릿 스쿱 수이며 $0 \le v, c \le 10000$이다.

각 데이터 집합마다 먼저 한 줄에 Data Set x:를 출력한다. 여기서 $x$는 1부터 시작하는 데이터 집합 번호다. 다음 줄에 모두가 원한 스쿱을 전부 받도록 하는 최소 총비용(센트)을 출력한다. 연속한 두 데이터 집합 사이에는 빈 줄 하나를 출력해 구분한다.