AT_pakencamp_2022_day1_f Events Scheduling

Pa 研合宿的 K 运营长希望决定在一天内举办哪些活动。 现在有 $N$ 个活动候选，Pa 研合宿的参与者有 $M$ 人。第 $i$ 个活动所需时间为 $L_i$。第 $i$ 个活动对于第 $j$ 位参与者带来的满意度为 $A_{i,j}$。 当你确定要举办至少 1 个活动时，这些活动集合的“良好度”被定义为：对每位参与者，选出的活动中该参与者的满意度的最大值之和。 由于一天的时长有限，举办所有活动所需的总时间不能超过 $D$。在此限制下，活动集合的“良好度”最多可以是多少？ 如果无法举办任何一个活动，请报告这一情况。

输入以如下格式从标准输入读入： > $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 只举办第二个活动是最优的选择。 ### 样例解释 2 无法举办任何活动。 ### 约束条件 - $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)$ - 输入均为整数。 由 ChatGPT 5 翻译