产品研发

一家公司正在研发一款新产品。该产品共有 K 项关键性能指标，初始时所有指标均为 0。公司的最终目标是让每一项指标都不低于 P。

研发团队提出了 N 个独立的改进方案。第 i 个方案一旦实施，会同时为第 j 项指标（1 ≤ j ≤ K）带来 A_{i,j} 的提升，但实施该方案需要投入 C_i 的研发成本。每个方案最多只能执行一次。

你需要判断：是否存在一系列方案的选择，使得所有指标均达到或超过 P？如果存在，请给出最小的总研发成本；如果不存在，输出 -1。

输入格式

第一行，三个整数 N, K, P，分别表示方案数量、指标数量和目标阈值。接下来 N 行，每行 K + 1 个整数 C_i, A_{i,1}, A_{i,2}, …, A_{i,K}，分别表示第 i 个方案的成本，以及执行后各指标的提升值。

输出格式

输出一个整数，表示达成目标所需的最小总成本。若无法达成，输出 -1。

输入样例1

4 3 5
5 3 0 2
3 1 2 3
3 2 4 0
1 0 1 4

输出样例1

9

输入样例2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

输出样例2

-1

说明提示

1 ≤ N ≤ 100

1 ≤ K, P ≤ 5

0 ≤ A_{i,j} ≤ P（1 ≤ i ≤ N, 1 ≤ j ≤ K）

1 ≤ C_i ≤ 10^9（1 ≤ i ≤ N）

限制

时间限制：1000ms，内存限制：128MiB