33155번 - 꽃바구니

문제

$N$개의 꽃과 $M$개의 바구니로 꽃바구니를 만들려 한다. 꽃바구니는 하나의 바구니와 하나 이상의 꽃으로 만들어진다. 꽃꽂이는 심오해서 꽃의 궁합을 잘 생각해야 한다. 궁합은 꽃 $i$와 꽃 $j$에 대해 정수 $C_{ij}$로 정의된다. 꽃바구니의 아름다움은 꽃바구니에 포함된 꽃 간 궁합의 합이다. 다시 말해, 어떤 꽃바구니 $S$의 아름다움은 다음과 같다.

$$\sum_\limits{i,j \in S;\ i \le j} C_{ij}$$

예를 들어 꽃 1,ドル 2$로 꽃바구니를 만든다면 그 아름다움은 $C_{11}+C_{12}+C_{22}$이다.

다음 규칙을 지키면서 꽃바구니의 아름다움의 합을 최대화해 보자.

• 각 꽃은 하나의 바구니에만 포함되거나 어떤 바구니에도 포함되지 않는다.
• 각 꽃바구니에 포함된 꽃의 크기 $A_i$의 합이 바구니의 크기 $B_j$를 넘을 수 없다.
• 각 꽃바구니에 포함된 꽃의 가치 $V_i$의 합이 판매할 가치 $K$를 넘으면 안 된다. 즉, 손해 보며 팔 수는 없다.

입력

첫 번째 줄에 꽃의 개수 $N,ドル 바구니의 개수 $M,ドル 판매할 가치 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 15; 1 \le M \le 200; 1 \le K \le 10^7)$

두 번째 줄에 꽃의 크기를 나타내는 정수 $A_1,A_2,\dots,A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^7)$

세 번째 줄에 바구니의 크기를 나타내는 정수 $B_1,B_2,\dots,B_M$이 공백으로 구분되어 주어진다. $(1 \le B_i \le 10^7)$

네 번째 줄에 꽃의 가치를 나타내는 정수 $V_1,V_2,\dots,V_N$이 공백으로 구분되어 주어진다. $(1 \le V_i \le 10^7)$

다섯 번째 줄부터 $N$개의 줄에 걸쳐 각 줄마다 $N$개의 정수가 공백으로 구분되어 주어진다. 그중 $i$번째 줄의 $j$번째 수는 꽃 $i$와 $j$의 궁합 $C_{ij}$이다. $(|C_{ij}| \le 10^7; C_{ij}=C_{ji})$

출력

완성한 꽃바구니의 아름다움의 최대 합을 출력한다.

제한

힌트