← 返回题目列表

AtCoder · pakencamp_2022_day1_f

F. 活动安排

中文机器翻译题面 查看原题

配点 : 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