Затоплені поля

Фермер Джон зіткнувся з проблемою: через дощ його пасовища можуть бути затоплені. На щастя, він встановив сучасну дренажну систему, яка підтримує однаковий рівень води по всій фермі. Проте, рельєф місцевості не на його боці. Корови фермера Джона можуть стояти лише на сухій землі: якщо земля затоплюється, корови на ній тонуть. На щастя, корови можуть переміщатися на один рядок щогодини, що дає їм шанс уникнути води (рівень якої піднімається і падає щогодини).

Фермер Джон розділив своє поле на рядки, які він індексує рядками та стовпцями. Кожен рядок досить малий, щоб вмістити лише одну корову.

Дано опис поля фермера Джона, початкові місця розташування його корів і висоту води кожну годину. Припускаючи, що корови фермера Джона надзвичайно розумні та передбачливі, і завжди можуть зробити найкращий хід, яка максимальна кількість корів фермера Джона може вижити?

Вхідні дані

У вхідних даних буде кілька тестових випадків. Кожен тестовий випадок починається з рядка з трьома цілими числами: n (1 ≤ n ≤ 100), k (0 ≤ k ≤ 100), і h (1 ≤ h ≤ 24), де n представляє розмір поля фермера Джона (це n×n рядків), k — кількість корів на полі, а h — кількість годин, які він повинен відстежувати.

Кожен з наступних n рядків міститиме по n цілих чисел, які представляють висоту кожного рядка поля фермера Джона (0 ≤ висота ≤ 100). Перший рядок у вхідних даних — це рядок 0, а останній — рядок n-1. Перший стовпець у кожному рядку — це стовпець 0, а останній — стовпець n-1.

Наступні k рядків кожен міститиме пару цілих чисел, r і c (0 ≤ r, c < n). Кожен рядок вказує позицію рядка однієї корови на годину 0, де r — це рядок, а c — це стовпець. Жодні дві корови не будуть в одній позиції.

Наступні h рядків кожен міститиме одне ціле число, яке вказує рівень затоплення на цю годину (0 ≤ рівень ≤ 100). Ці рядки подані в порядку: спочатку година 1, потім година 2 і так далі. Зверніть увагу, що час починається з години 1, а позиції корів подані на годину 0, тому корови мають можливість рухатися (або МУУУвитися) перед першим затопленням. Рядок вважається затопленим, якщо його висота ≤ рівень затоплення на дану годину.

Вхідні дані закінчуються рядком з трьома 0.

Вихідні дані

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