| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 255 | 90 | 77 | 38.119% |
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가 얻을 수 있는 최대 공격력 증가량을 출력한다.
20 3 3 2 4 7 5 2 3 4 6 8 7 1 2 3 4 6 8 11 2 4 6 1 10 3 3 5 8 2 2 2 0 0 0 2 3 0 0 0 3 3 1 1 2 6 8 0 1 3 0 0 1 0 4 1 0 2 6 7 1 0 2 0 1 2 0 2 1 0
37
Cube219가 방어구를 착용할 수 없을 수도 있음에 유의하라.
또한 Python 사용자는 PyPy3로 제출하는 것을 권장한다.