Задача G. Оптимизация ≡

Автор:	Жюри ВКОШП-2008		Ограничение времени:	2 сек
Входной файл:	optimize.in		Ограничение памяти:	256 Мб
Выходной файл:	optimize.out

Условие

В компании "QQQ" работает n человек. Очередной проект компании состоит из m независимых частей. Управляющий компании оценил время, которое требуется для выполнения каждой из частей проекта (предполагается, что это время не зависит от того, кто будет выполнять эту часть). После чего он некоторым образом распределил все m частей между n работниками. В результате оказалось, что некоторым из работников потребуется потратить на выполнение своей работы больше времени, чем другим (поскольку им досталась более объемная работа).

Поэтому управляющий решил улучшить распределение работ следующим образом: выбрать двух различных работников и выбрать одну из частей проекта, назначенную первому работнику, и одну из частей, назначенную второму. После этого часть проекта, назначенную первому работнику, назначить второму, а часть, назначенную второму, — назначить первому. Если в результате этой операции максимум из времен выполнения работы первым и вторым работниками уменьшился, то такую операцию назовем оптимизирующей.

Например, пусть проект состоит из пяти частей со временами выполнения 3, 6, 4, 8, 2, и в компании есть три работника. Пусть распределение работ выглядит следующим образом: первый работник — части 1 и 2 (суммарное время 3 + 6 = 9), второй работник — часть 4 (суммарное время 8) и третий работник  — части 3 и 5 (суммарное время 4 + 2 = 6). Тогда если первое задание (назначенное первому работнику) назначить третьему, а пятое задание (назначенное третьему) назначить первому, то у первого работника суммарное время станет равно 6 + 2 = 8, а у третьего — 3 + 4 = 7. Поскольку max(9, 6) > max(8, 7), то эта операция будет оптимизирующей.

Вам дано число работников в компании, число частей в проекте, время, необходимое на выполнение каждой из частей проекта и распределение частей по работникам. Требуется посчитать число различных возможных оптимизирующих операций в данном распределении работ.

Формат входного файла

Первая строка входного файла содержит два натуральных числа n и m — число работников в компании и число частей в проекте соответственно. Вторая строка содержит m натуральных чисел — i-ое число равно времени выполнения i-ой части проекта (части проекта нумеруются, начиная с 1). Времена выполнения частей не превосходят 10⁹. Далее идут n строк, описывающих распределение частей по работникам. Каждая строка содержит описание частей проекта, которые получил соответствующий работник. Описание состоит из числа частей, которые достались работнику, и их номеров.

Формат выходного файла

В выходной файл выведите искомое число оптимизирующих операций.

Во втором примере любая операция является оптимизирующей.

Ограничения

1 ≤ n, m ≤ 10⁵

Примеры тестов

№	Входной файл (optimize.in)	Выходной файл (optimize.out)
1	3 5 3 6 4 8 2 2 1 2 1 4 2 3 5 скопировать	2 скопировать
2	2 4 1 2 3 4 2 1 2 2 3 4 скопировать	4 скопировать

---