$$$\qquad$$$Старший Координатор Библброкс очень любит играть в Космическое Го и, между прочим, очень не любит проигрывать. По правилам Космического Го, игральным полем является прямоугольный гобан, расчерченный вертикальными и горизонтальными линиями. Стандартный космический гобан состоит из $$$N$$$ x $$$N$$$ ячеек в декартовой системе координат $$$(x, y)$$$, где $$$(1 \leq x, y \leq N)$$$.

$$$\qquad$$$В каждой ячейке может находиться один из трех объектов: заблокированная ячейка, игровая ячейка или Го-иси. Окрашены они в красный, зеленый и белый цвета соответственно. Для каждого $$$i$$$, $$$(1 \leq i \leq N)$$$, в $$$i$$$-той колонке, ячейки с самого нижнего ряда до $$$A_i$$$-того ряда снизу — красные ячейки, которые обозначают заблокированные поля.

$$$\qquad$$$Существует $$$M$$$ белых ячеек, которые обозначают Го-иси. У каждого Го-иси есть своя целочисленная положительная цена удаления с игрового поля. Каждая $$$j$$$-тая белая ячейка $$$(1 \leq j \leq M)$$$ является ячейкой $$$(X_j, Y_j)$$$. Все остальные ячейки являются зелеными и обозначают свободные ячейки.

Некоторый прямоугольный участок поля считается защищенным если на нём:

$$$\qquad$$$1. Отсутствуют красные ячейки.

$$$\qquad$$$2. Находится 2 и более белых Го-иси.

$$$\qquad$$$Чтобы победить, Библброксу необходимо удалить все защищенные участки (одно удаление является одним ходом). Библброкс хочет всегда ставить рекорды, а чтобы получить наилучший результат, ему необходимо добиться минимальной стоимости всех ходов. Библброксу тяжело вычислять защищенные участки, и он просит нас написать программу, которая поможет ему выявлять и разрушать защищенные участки.

$$$\qquad$$$Вы конечно же вызвались помочь Библброксу в решении столь интересной задачи.