У нас є сітка з \(H\) горизонтальними рядками і \(W\) вертикальними стовпцями. Нехай (\(i, j\)) позначають комірку в \(i\)-му рядку і \(j\)-му стовпці. (\(i, j\)) містить ціле число \(A_{i,j}\). Степан вийде з (1, 1) і певну кількість разів переміститься на один квадрат праворуч або вниз, поки не досягне (\(H, W\)). Не дозволяється виходити з сітки.

Вартість цього походу визначається як:

• сума найбільших цілих \(K\) чисел серед цілих чисел, записаних на пройдених \(H+W-1\) комірках.

Знайдіть мінімально можливу вартість походу Степана.

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

Перший рядок містить цілі числа \(H,W,K\) (\(1 \le H,W \le 30\), \(1 \le K < H+W\))

Наступні  \(H\) рядків містять ао \(W\) цілих чисел \(A_{i,j}\) (\(1 \le A_{i,J} \le 10^9\))

Числа у рядках розділяються пропуском.

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

У вихідний потік виведіть шукану вартість.

Примітка

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

Існує лише один спосіб пересування, де пройдені квадрати містять цілі числа 5, 4, 3 від найбільшого до найменшого, тому виводими 9(=5+4).

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

1 3 2
3 4 5

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

9

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

2 2 1
3 2
4 3

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

3

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

3 5 3
4 7 8 6 4
6 7 3 10 2
3 8 1 10 4

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

21