IOI 사진

올란디카(Olandica) IOI 팀의 네 멤버 샤보르즈(Shaborz), 호이딘(Hoidin), 알세인(Alssein), 아얀(Ayan)은 2004년 아테네 IOI를 마치고 돌아온 날 가을 학기 수업에 참석했다. 아테네에 머무는 동안 이들은 히드라 섬, 개회식, 시상식과 폐회식, 아테네 시내 등 여러 장소와 행사에서 많은 사진을 찍었다. 하지만 첫 대학 생활에 들뜬 나머지, 마침 ACM 지역 대회 기간과 겹친 중간고사 휴식 기간이 되어서야 사진을 떠올렸다. 이제 이들은 사진을 인화해 각자 자신만의 IOI 앨범을 만들고 싶어 한다.

여러 개의 필름 롤이 있으며, 각 롤에는 하나의 장소 또는 행사에서 찍은 사진만 들어 있다. 같은 장소나 행사의 사진이 서로 다른 여러 롤에 담겨 있을 수도 있다. 각 롤에는 1번부터 36번까지 번호가 매겨진 최대 36장의 네거티브가 들어 있다. 팀 멤버와 친구들은 사진 인화를 주문한다. 샤보르즈는 모든 주문을 모아 인화소와 다음과 같이 계약한다.

• 사진 한 장을 인화하면 $S$ Rial이 든다.
• 한 롤의 모든 사진을 인화하면 $R$ Rial이 든다.
• 한 번의 주문으로 모든 롤의 모든 사진을 인화하면 $A$ Rial이 든다.

샤보르즈는 주문 목록을 받아 전체 인화 비용을 최소화하려고 한다. 하나의 롤은 (장소 이름, 롤 번호) 쌍으로 구분된다. 최소 비용을 얻기 위해서라면 필요한 것보다 더 많은 사진을 인화해도 된다.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 네 개의 정수 $N$ ($1 \le N \le 100$), $S$, $R$, $A$가 주어진다. $N$은 주문의 수이고, $S$, $R$, $A$는 각각 사진 한 장, 한 롤 전체, 모든 롤 전체를 인화하는 비용이다.

이어서 $N$개의 줄이 주어지며, 각 줄은 한 명의 고객(팀 멤버 또는 친구)이 낸 주문 하나를 나타낸다. 주문 줄은 공백으로 구분된 여러 항목으로 이루어진다. 각 항목은 PlaceName:RollNo:FromPhoto..ToPhoto 형식이다.

• PlaceName은 최대 100자의 문자열이며 대소문자를 구별한다.
• RollNo는 해당 장소의 여러 롤 중 원하는 롤을 지정하며 1 이상 10 이하이다.
• FromPhoto와 ToPhoto는 인화할 사진의 범위를 나타내며 1 ≤ FromPhoto ≤ ToPhoto ≤ 36 을 만족한다.

장소는 최대 20개라고 가정해도 된다. 한 롤에서 사진 한 장만 필요한 경우, 형식을 PlaceName:RollNo:PhotoNo로 간단히 쓸 수 있다. 모든 비용은 음이 아닌 정수이다.

각 테스트 케이스마다, 원래 주문 집합의 모든 사진을 인화하는 최소 비용을 나타내는 정수 하나를 한 줄에 출력한다.