配点 : 300 点
問題文
K是训练营的经理,他想决定有一天要举办什么样的活动。 有
現在 N 个赛事候选人,PA训练营的参加者有 M 人。 i 事件持续时间为 L_i 。另外,i 活动 j 第 名参与者的满意度为 A_{i,j} 。
1 或更多事件时,事件集的优度被定义为所有人对该事件的最大满意度的总和。
由于一天中的小时数有限,因此事件的总时间长度为 必须小于或等于 D 。在这种情况下,要执行的一组事件的最大优点是多少?
但是,如果您无法执行任何活动,请报告此情况。
制約
- 1 \leq N,M \leq 18
- 1 \leq D \leq 10^9
- 1 \leq L_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq A_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M D
L_1 L_2 \cdots L_N
A_{1,1} A_{1,2} \cdots A_{1,M}
A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,M}
出力
善良的最大价值
在 1 行输出。如果您无法举办任何活动 -1 请输出
入力例 1
2 4 10 5 6 1 2 3 4 5 6 7 8
出力例 1
26
最好只做第二个事件。
入力例 2
1 4 10 11 3 6 1 8
出力例 2
-1
无法执行事件。
入力例 3
4 8 100 30 40 50 110 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
54