Задача Friends. Троє колишніх переможців олімпіад з інформатики вирiшили створити стартап. Сучасних iнвесторiв складно зацiкавити нейронними мережами чи блокчейном, тож замiсть цього хлопцi вирiшили створити аеропорт для квадрокоптерiв. Для цього молодики знайшли дiлянку розмiром N на N метрiв. Студенти живуть лише на стипендiю, тож змушенi купувати землю по одному квадратному метру щомiсяця. Щоб максимально ефективно використовувати бюджет, хлопцi скористались останнiми розробками в нейронних мережах та передбачили цiни на найближчий час. Пiсля цього вони склали графiк закупiвлi землi. Усiм вiдомо, що найголовнiша частина аєропорту — це злiтна смуга. Мiжнароднi стандарти вимагають, щоб злiтна смуга мала форму прямокутника, що має розмiр A на B. Для полегшення роботи авiадиспетчера злiтна смуга буде розмiщена паралельно однiй з сторiн. Як тiльки буде побудована злiтна смуга, можна починати наступний раунд iнвестицiй i запрошувати мiжнародних експертiв. Їх цiкавить наступне питання: через скiльки мiсяцiв буде куплена земельна дiлянка, достатня для побудови злiтньої смуги. Звiсно, що будувати студентам дозволено лише на куплених дiлянках. Писати нейроннi мережi хлопцi навчились, а як розв’язувати алгоритмiчнi задачi вже підзабули (бізнес!), тому й просять вас допомогти.
Технічні умови. Програма Friends читає з пристрою стандартного введення в першому рядку числа N,A,B(1 ≤ N ≤ 1000,1 ≤ A,B ≤ N - розмiри. В наступних N рядках рiвно по N рiзних натуральних чисел, кожне не перевищує N2. Кожне число задає номер мiсяця, у якому буде придбана вiдповiдна дiлянка землi.
Програма виводить єдине число - мiнiмальний номер мiсяця, в якому з’явиться місце для побудови злітної смуги.
Приклад
Введення
5 2 3
3 13 14 15 18
20 11 7 10 16
12 2 4 8 17
5 9 6 19 1
21 24 25 23 22 |
Виведення
11 |
Пояснення до прикладу
Через 10 мiсяців «мапа» куплених земельних дiлянок буде виглядати наступним чином (символ X позначає придбанi дiлянки, . - ще не придбанi):
X . . . .
. . X X .
. X X X .
X X X . X
. . . . .
На 11 мiсяцi купується дiлянка:
X . . . .
. X XX .
. X XX .
X X X. X
. . . . .
|
|