꽃바구니

$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})$

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