25906번 - 수렵의 시간이다!

Cube219는 최근 M게임을 즐겨한다. M게임에는 스킬이라는 특수한 시스템이 존재한다. 스킬은 $5$개가 있으며, 각 스킬에는 최대 레벨과 $1$레벨부터 레벨마다 부여된 공격력 증가량이 있다. 처음에 스킬들의 레벨은 전부 $0$이다. 이러한 스킬들의 레벨은 방어구를 착용하면 올릴 수 있다. 방어구는 머리, 상의, 하의 총 $3$종류가 있으며, 종류마다 최대 $1$개의 방어구를 착용할 수 있다. 각 방어구에는 특정 스킬들의 레벨 증가량이 부여되어 있다. 스킬의 레벨이 최대 레벨을 넘을 경우 공격력 증가량은 최대 레벨에 부여된 것을 따른다.

수렵을 하면서 골드를 모은 Cube219는 더 강해지기 위해 방어구를 파는 상점에 갔다. 상점에는 $M$개의 방어구를 각각 $c_i$골드로 팔고있다.

여기에 추가로, 상점에서는 강화를 $K$골드를 지불하고 전체 방어구 중 최대 한 개의 방어구에 할 수 있는데, 강화를 하면 방어구에 부여된 스킬 레벨 증가량 중 하나를 $1$ 감소시키고 원하는 스킬의 레벨 증가량 중 하나를 $1$ 증가시킬 수 있다. 여기서 방어구에 $1$이상 부여된 스킬 레벨 증가량만 감소시킬 수 있으며, 부여되지 않은 스킬의 레벨도 증가시킬 수 있다.

Cube219는 처음에는 아무 방어구도 착용하고 있지 않다. Cube219가 가지고 있는 돈과 구입할 수 있는 방어구 목록이 있을 때, 얻을 수 있는 최대 공격력 증가량을 구하여라.

첫 번째 줄에 가지고 있는 돈 $T$와 강화 비용 $K$가 공백으로 구분되어 주어진다. $(0 \leq T,K \leq 100\,000)$

다음 $5$개의 줄에 $i$번 스킬의 최대 레벨 $l_i$와 이어서 $l_i$개의 정수 $a_{i,1},\cdots,a_{i,l_i}$가 공백으로 구분되어 주어진다. $(1 \leq l_i \leq 100;$ $1 \leq a_{i,j} \leq 100\,000;$ $a_{i,j} \leq a_{i,j+1})$ $a_{i,j}$는 $i$번 스킬이 $j$레벨일 때 공격력 증가량이다.

다음 줄부터는 순서대로 머리, 상의, 하의 총 $3$종류의 방어구의 정보가 주어진다.

방어구 정보의 첫 번째 줄에는 방어구의 개수 $M$이 정수로 주어진다. $(1 \leq M \leq 50)$

방어구 정보의 다음 줄에는 $M$개의 정수 $c_1,\cdots,c_M$이 공백으로 구분되어 주어진다. $(1 \leq c_i \leq 100\,000)$ $c_i$는 $i$번째 방어구의 가격이다.

방어구 정보의 다음 $M$개의 줄에는 $5$개의 정수 $v_{i,1},\cdots,v_{i,5}$가 공백으로 구분되어 주어진다. $(0 \leq v_{i,j} \leq l_j)$ $v_{i,j}$는 $i$번째 방어구의 $j$번 스킬 레벨 증가량이다. $v_{i,j}$가 $0$이면 $j$번 스킬 레벨 증가량이 부여되지 않은 것이다.

Cube219가 얻을 수 있는 최대 공격력 증가량을 출력한다.

Cube219가 방어구를 착용할 수 없을 수도 있음에 유의하라.

또한 Python 사용자는 PyPy3로 제출하는 것을 권장한다.