Дмитрик, новачок в олімпіадному програмуванні, хоче вивчити \(M\) алгоритмів. Спочатку його рівень розуміння кожного з \(M\) алгоритмів дорівнює 0. Дмитрик відвідує книжковий магазин, де продаються \(N\) книг про алгоритми. \(I\)-та книга (\(1\leq i\leq N\)) продається за \(C_i\) грн. Якщо він купить і прочитає її, то його рівень розуміння \(j\)-го алгоритму підвищиться на \(A_{i,j}\) для кожного \(j\) (\(1\leq j\leq M\)). Іншого способу підвищити рівень розуміння алгоритмів немає.

Мета Дмитрика — зробити рівень розуміння всіх \(M\) алгоритмів \(X\) або вище. Визначте, чи досяжна ця мета. Якщо це досяжно, знайдіть мінімальну суму грошей, необхідну для цього.

Формат вхідних даних

Перший рядок містить цілі числа \(N,M,X\) (\(1 \le N,M \le 12\), \(1 \le X \le 10^5\))

Наступні  \(N\) рядків містять цілі числа \(C_i, A_{i1}, A_{i2}, ... A_{iM}\) (\(1 \le C_i \le 10^5\), \(0 \le A_{ij} \le 10^5\), \(1 \le j \le M\))

Формат вихідних даних

У вихідний потік виведіть мінімальну суму грошей або -1, у випадку недосяжної мети.

Примітка

До прикладу 1:

Купівля другої та третьої книг забезпечує йому рівень розуміння всіх алгоритмів 10 або вище, за мінімально можливих витрат.

Приклад вхідних даних

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

Приклад вихідних даних

120

Приклад вхідних даних

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

Приклад вихідних даних

-1

Приклад вхідних даних

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Приклад вихідних даних

1067