Задача 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 . . . . На 11 мiсяцi купується дiлянка: |