합작 투자

대형 국책 사업은 보통 필요한 전문성과 투자 규모가 서로 다른 여러 모듈로 나뉜다. 그래서 한 회사가 사업 전체를 혼자 끝내기는 어렵고, 두 회사 이상이 전문 인력과 자원을 나눠 맡는 합작 방식이 흔하다. 다만 합작 이익을 최대로 만드는 일은 따져야 할 조건이 많아 간단하지 않다. 프로그램이 필요한 지점이 여기다.

A사와 B사가 $D$일 안에 끝내야 하는 사업을 함께 맡았다. 사업은 $M$개의 모듈 $L_1, L_2, \dots, L_M$으로 이루어진다. $L_1$을 가장 먼저 끝내야 하고, $i \ge 1$인 모듈 $L_i$를 끝내야 $L_{i+1}$을 시작할 수 있다. $L_i$가 끝난 다음 날 바로 $L_{i+1}$을 시작하므로, 사업 전체에 걸리는 기간은 각 모듈에 걸리는 일수의 합이다. 한 모듈은 A사와 B사 중 한 곳만 맡는다.

두 회사의 전문 분야가 다르므로, 어떤 모듈은 A사가 짧은 기간과 적은 비용으로 끝내지만 B사는 훨씬 오래 걸리고 비용도 많이 드는 경우가 있고 그 반대도 있다. 한 회사가 특정 모듈을 아예 맡지 못하는 경우도 있다. 그러면 다른 회사가 그 모듈을 맡아야 사업을 끝낼 수 있다.

두 회사가 투자할 수 있는 금액에는 한도가 있다. A사가 부담하는 비용의 합은 $K_A$ 이하, B사가 부담하는 비용의 합은 $K_B$ 이하여야 한다. 정부가 지급하는 사업비가 $R$일 때 이익은 $R$에서 두 회사가 쓴 비용의 합을 뺀 값이다. $M$개의 모듈을 모두 $D$일 안에 끝내면서 이익을 최대로 만드는 분담을 구하여라.

첫째 줄에 A사와 B사가 함께 맡은 사업의 수 $T$ ($T \le 10$)가 주어진다. 이어서 사업마다 다음 자료가 주어진다. 같은 줄에 있는 수는 공백 하나로 구분된다.

• 첫째 줄에 정수 $D$, $M$, $R$가 주어진다. $1 < D \le 200$, $1 < M \le 40$, $1 < R \le 100$이고, $R$은 정부가 이 합작 사업에 지급하는 사업비로 단위는 백만 바트다.
• 둘째 줄에 $K_A$와 $K_B$가 주어진다. 각각 A사와 B사가 이 사업에 투자할 수 있는 총액이고, 단위가 백만 바트인 양의 정수이며 $K_A, K_B \le 40$이다.
• 셋째 줄에 정수 $M$개가 주어진다. A사가 각 모듈을 끝내는 데 걸리는 일수이며, 첫 번째 수가 모듈 1, 두 번째 수가 모듈 2에 해당한다. A사가 그 모듈을 맡지 못하면 $-1$이고, 맡을 수 있으면 양의 정수다.
• 넷째 줄은 셋째 줄과 형식이 같고 B사의 자료다.
• 다섯째 줄에 정수 $M$개가 주어진다. A사가 각 모듈을 끝내는 데 드는 비용이며 단위는 백만 바트다. 순서는 셋째 줄과 같다. A사가 그 모듈을 맡지 못하면 $-1$이고, 맡을 수 있으면 양의 정수다.
• 여섯째 줄은 다섯째 줄과 형식이 같고 B사의 자료다.

어떤 회사가 특정 모듈을 맡지 못하면 그 모듈의 일수와 비용이 모두 $-1$로 주어진다.

사업 $1, 2, \dots, T$의 최대 이익을 순서대로 한 줄에 출력한다. 값은 공백 하나로 구분하고 줄 끝에는 줄바꿈을 넣는다.

두 회사 모두 맡지 못하는 모듈이 있거나 어떻게 분담해도 $D$일 안에 끝낼 수 없으면 그 사업의 값으로 $-1$을 출력한다. 이익이 남지 않는 경우, 즉 손실이거나 이익이 0인 경우에도 $-1$을 출력한다. 그 밖에는 최대 이익을 백만 바트 단위로 출력한다.