케이크

동네 빵집이 앞으로 몇 달 동안의 사업 계획을 세우고 있다. 제빵사들은 $C$가지 서로 다른 레시피를 가지고 있으며, 각 레시피마다 필요한 재료와 도구가 정해져 있다. 재료는 빵을 구울 때 소모되지만 도구는 소모되지 않아서 다른 레시피에도 다시 쓸 수 있다. 지금 빵집에는 재료도 도구도 없다. 홍수로 모두 잃었거나 세무서가 가져갔다.

주방장의 아들은 케이크 종류마다 한 번씩만 굽자고 모두를 설득했다. 인터넷 사용자들은 자신만의 고유한 Nutty-Fudge Tart(NFT)를 단독으로 소유하려고 추가 금액을 기꺼이 낼 것이라고 한다. 아들은 이미 케이크 종류마다 벌 수 있는 금액을 추정해 두었다. 제빵사들은 서로 눈치를 보며 어떤 케이크를 만들어야 이익이 최대가 될지 고민하고 있다. 모든 재료와 도구의 가격, 그리고 케이크 가격이 주어졌을 때, 제빵사들이 낼 수 있는 최대 이익을 구하라.

첫째 줄에 세 정수 $G$, $C$, $T$가 주어진다. 각각 재료의 개수, 레시피의 개수, 도구의 종류 수이다. 둘째 줄에는 케이크의 가격 $c_1, \ldots, c_C$가 $C$개의 정수로 주어진다. 셋째 줄에는 재료의 가격 $g_1, \ldots, g_G$가 $G$개의 정수로 주어진다. 넷째 줄에는 도구의 가격 $t_1, \ldots, t_T$가 $T$개의 정수로 주어진다.

이어서 $C$개의 줄에 걸쳐 각 줄마다 $G$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 케이크 $i$에 들어가는 재료 $j$의 양 $a_{i,j}$이다.

마지막 $C$개의 줄은 도구 정보이다. $i$번째 줄은 케이크 $i$에 필요한 도구의 개수 $n_i$로 시작하고, 이어서 $n_i$개의 서로 다른 정수 $b_{i,k}$가 나온다. 이것이 케이크 $i$를 만들 때 필요한 도구이다.

최대 이익을 나타내는 수 하나를 출력한다.

• $1 \leq G, C, T \leq 200$
• $0 \leq c_i, t_i \leq 10^9$
• $0 \leq g_j, a_{i,j} \leq 10^8$
• $0 \leq n_i \leq T$
• $1 \leq b_{i,k} \leq T$

최대 이익은 케이크 1번과 2번을 굽고 3번은 굽지 않을 때 얻어진다.