경기 부양책

경제 위기의 충격을 완화하기 위해 정부가 대규모 경기 부양책을 통과시켰다. 민간 투자가 위축된 상황에서 정부가 직접 가치 있는 사업에 투자하여 일자리를 만들고 경제 회복을 돕겠다는 것이다. 어떤 사업에 예산을 배정할지는 어려운 결정이다. 사업마다 만들어 내는 일자리 수, 비용, 그리고 남는 사회 기반 시설(인프라)의 크기가 다르기 때문이다. 어떤 사업은 (다리 건설처럼) 즉시 일자리를 만들고, 어떤 사업은 (연구처럼) 몇 년 뒤에야 일자리를 만든다.

각 사업 $i$에는 비용 $c_i$, 인프라 이득 $g_i$, 그리고 앞으로 $Y$년 동안 해마다 만들어 내는 일자리 수 $j_{i,1}, j_{i,2}, \ldots, j_{i,Y}$가 주어진다. 또한 전체 예산 $B$와 연도별 일자리 목표 $J_1, J_2, \ldots, J_Y$가 주어진다.

총비용이 $B$를 넘지 않으면서, 매년 $t$마다 만들어 내는 일자리의 합이 목표 $J_t$ 이상인 (즉, 모든 $t$에 대해 $\sum_{i \in S} j_{i,t} \ge J_t$) 사업들의 집합 $S$를 고르려 한다. 이러한 집합 가운데 인프라 이득의 합 $\sum_{i \in S} g_i$의 최댓값을 구하여라. 예산 안에서 모든 연도의 일자리 목표를 만족하는 집합이 하나도 없다면 그 사실을 출력한다.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. 각 데이터 집합은 다음과 같은 형식이다.

• 첫 줄에 세 정수 $n$, $Y$, $B$가 주어진다. $n$은 고려하는 사업의 수로 $n \le 20$, $Y$는 내다보는 미래의 햇수로 $1 \le Y \le 50$, $B$는 전체 예산으로 $0 \le B \le 10^9$이다.
• 다음 줄에 연도별 일자리 목표 $J_1, \ldots, J_Y$를 나타내는 $Y$개의 정수가 주어진다.
• 이어지는 $n$개의 줄에는 각 사업이 $Y + 2$개의 정수로 주어진다. 먼저 그 사업의 연도별 일자리 수 $j_{i,1}, \ldots, j_{i,Y}$, 그다음 사업의 비용 $c_i$, 마지막으로 인프라 이득 $g_i$이다.

각 데이터 집합마다 먼저 Data Set x: 형식의 줄을 출력한다. 여기서 x는 그 데이터 집합의 번호(1부터 시작)이다. 다음 줄에는, 예산 안에서 모든 일자리 목표를 만족하는 집합이 없으면 No selection. 을, 그렇지 않으면 가능한 인프라 이득 합의 최댓값을 출력한다. 서로 다른 데이터 집합 사이는 빈 줄로 구분한다.