Ampelmännchen

두 나라가 통일하면 도로 표지판, 피클, 케첩처럼 일상적인 물건은 대부분 나라마다 방식이 따로 있다. 한쪽이 자기 방식을 그대로 강요하면 다른 쪽은 대등한 통합이 아니라 병합이라고 느낀다. 실제로 동독 사람 다수가 독일 통일 과정을 그렇게 받아들였고, 새 나라에 정을 붙이기까지 오래 걸렸다. 오래 가는 통합은 양쪽에서 조금씩 가져와 만든다.

한쪽 방식이 더 낫다는 데 양쪽 생각이 같을 때도 있다. 보행 신호등에 서 있는 사람 모양인 동독의 Ampelmännchen은 모두가 좋아했다. 어려운 쪽은 각자 자기 방식을 더 좋아하는 경우다. 이때는 "피클은 우리가 아주 중요하게 여기니 우리 것으로 하자, 대신 케첩은 너희 것도 우리 것만큼 괜찮으니 너희 것으로 하자" 같은 절충이 필요하다.

논쟁이 되는 물건 목록이 주어진다. 물건마다 두 나라가 각 방식을 얼마나 좋아하는지 알고 있고, 두 나라에 각각 몇 명이 사는지도 알고 있다. 어떤 방식이 뽑히든 한 나라 사람은 모두 자기 나라가 말한 선호도만큼 만족한다. 물건마다 두 방식 중 정확히 하나를 고른다. 모든 사람과 모든 물건에 대해 더한 만족도의 총합을 최대로 만들어라.

정리하면, 어떤 물건에서 서쪽 방식을 고르면 총합에 $W \cdot L_{w,w} + E \cdot L_{e,w}$이 더해지고, 동쪽 방식을 고르면 $W \cdot L_{w,e} + E \cdot L_{e,e}$이 더해진다.

첫 줄에 파일에 들어 있는 데이터 집합의 개수 $K \ge 1$이 주어진다. 이어서 데이터 집합 $K$개가 주어진다.

각 데이터 집합의 첫 줄에는 정수 세 개 $n$, $W$, $E$가 주어진다. $0 \le n \le 1000$은 논쟁이 되는 물건의 수이고, $0 \le W, E \le 10000$은 서쪽과 동쪽에 사는 사람 수다.

다음 $n$개 줄에는 각각 정수 네 개 $L_{w,w}$, $L_{w,e}$, $L_{e,w}$, $L_{e,e}$가 주어지며 모두 0 이상 100 이하다. 순서대로 서쪽이 자기 방식을 좋아하는 정도, 서쪽이 동쪽 방식을 좋아하는 정도, 동쪽이 서쪽 방식을 좋아하는 정도, 동쪽이 자기 방식을 좋아하는 정도다.

데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 1부터 세는 데이터 집합 번호다. 다음 줄에 물건마다 방식을 정확히 하나씩 골라서 얻을 수 있는 최대 만족도 총합을 출력한다. 데이터 집합을 출력한 뒤에는 빈 줄을 하나 출력한다.