В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом (Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова, a, ab и aba являются префиксами слова aba) другого. Например, набор слов aba, aa и bac является беспрефиксным кодом, а набор abac, aba, ba нет, поскольку слово aba является префиксом слова abac.

Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор abac, abс, ba является почти беспрефиксным кодом уровня 2, а набор abac , abab, ba нет, поскольку наибольший общий префикс слов abac и abab имеет длину 3.

Очередная задача, которую профессор Дешифро поставил своим лаборантам, заключается в следующем: по заданному набору слов и числу k требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня k. Вам, как младшему лаборанту, поручили написать соответствующую программу.

В компании 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), то эта операция будет оптимизирующей.

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