시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

문제

Ивайло всяка седмица участва в състезания по информатика, които протичат по следните правила.

На участниците се предлагат за решаване N задачи. Когато решат една задача, състезателите я пращат в системата за тестване. По време на състезанието се извършва проверка с малък набор от тестове, наречени предшественици. Резултатът от проверката на решението с предшествениците се съобщава на участника веднага след проверката. Ако програмата е дала верен резултат на всички тестове, тогава на участника се присъждат предварителни точки за съответната задача. След това участникът може да блокира тази задача, за да има възможност да наблюдава решенията на другите участници по задачата.

Участник може да хакне решението на друг участник. В този случай хакнатото решение няма да донесе нито една точка на автора си, а хакващото решение ще получи 100 точки. Ако решението не е хакнато и след края на състезанието преминава пълния набор от тестове, то участникът ще получи предварително спечелените точки по задачата. В края на състезанието се изчислява общият брой точки, събрани от всеки участник за решаване на задачите и за хакване. Победител е участникът с най -много точки.

Остават само пет минути до края на състезанието. Ивайло вече е решил всички задачи, които е можел да направи (освен това неговите решения ще преминат пълния набор от тестове след края на състезанието) и той ги блокира. Сега той може да се изкачи в класирането само чрез хакване решенията на другите участници.

Треньорът на Ивайло изисква той да е на първо място еднолично. Ако Ивайло заеме място, различно от първото (или споделя първото с друг участник), ще бъде наказан - лишен от възможността да направи няколко компютърни игри. Естествено, Ивайло е малко мързелив и винаги се опитва да постигне желания резултат с минимални усилия.

Вие може да му помогнете, като напишете програма hacks, която намира минималния брой хаквания, които Ивайло трябва да направи, за да излезе на първо място. Ако е невъзможно да излезе на първо място, отпечатайте числото −1.

Ще приемем, че Ивайло може да хакне всяко решение на всеки участник и всички решения, които не са хакнати от него, ще преминат пълния набор от тестове (като по този начин ще донесат точки на съответния участник). Ивайло е толкова силен в програмирането, че може да извършва хакване моментално, т.е. за останалите пет минути може да хакне неограничен брой задачи. Ивайло може да разбие решения на други участници само на онези задачи, които самият той е решил.

입력

На първия ред на стандартния вход са записани три цели числа − брой на задачите N, брой на участниците M и поредния номер на Ивайло в текущата таблица с резултатите K (таблицата с резултатите не е сортирана по предварителните точки на участниците).

Във всеки от следващите M реда са записани по N цели числа, като на i-тия от тези редове (i = 1,... , M) са записани стойностите Aij, j=1,.. , N – предварителни точки на i-тия участник за задача j. Ако Aij = 0, това означава, че този участник още не е предал задача j или неговото решение не е минало с тестовете предшественици.

출력

На първия ред на стандартния изход програмата трябва да изведе едно цяло число – минималния брой хаквания, които трябва да направи Ивайло, за да излезе еднолично на първо място или числото -1, ако това е невъзможно.

제한

  • 1 ≤ N ≤ 50
  • 1 ≤ M ≤ 10 000
  • 1 ≤ K ≤ M
  • 0 ≤ Aij ≤ 10 000 000

예제 입력 1

5 3 3
500 500 0 0 500
300 0 0 0 0
480 500 0 0 490

예제 출력 1

1

예제 입력 2

5 4 3
500 500 500 500 500
500 500 500 400 500
500 500 500 500 200
500 500 350 500 500

예제 출력 2

2

예제 입력 3

3 3 1
0 0 0
0 0 0
0 0 0

예제 출력 3

-1

힌트

В първия пример Ивайло може да хакне решението на първа задача на втория участник, за което ще получи 100 точки и ще излезе на първо място с 480 + 500 + 490 + 100 = 1 570 точки.

Във втория пример Ивайло трябва да хакне решенията на двама състезатели, тогава той ще спечели 500 + 500 + 500 + 500 + 200 + 100 + 100 = 2400 точки и ще излезе начело.

В третия пример Ивайло не може да спечели нито една точка, тъй като нито един участник не е решил нито една задача и всички състезатели споделят първото място. Така че отговорът е -1.