#PY0020. 算法学习

算法学习

Description

小J准备这个假期学习M种算法

现在他看中了N本书,准备从这些书中选一些来买

他的目标是看完这些书后,他对这M种算法的理解力都要大于等于X

对于第i本书,其价格为Ci,看完它后,对每种算法均会有所提升量,这个输入的时候会给出。

Format

Input

第一行给出N,M,X

接下来N行,每行首先给出Ci,再给出这本书对从第1种算法到第M算法的提升值。

N,M<=12

其它值均<=1e5

Output

问最少要花多少钱,无解输出-1

Samples

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9
120

Hint

买第二本和第三本书即可