Республиканская олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

Задача B. Array

Дан массив $a$ длины $k$. Так же, имеются $n$ массивов длины $k$. Массив $x$ называется хорошим, если существует перестановка $p$ длины $k$, такая что для каждого $i$ $(1 <= i <= k)$ выполняется $x_{p_i} \equiv 0 \pmod{a_i}$.

Вам необходимо посчитать количество пар $(l, r)$ $(1 <= l <= r <= n)$, таких что количество хороших массивов в отрезке больше чем нехороших.

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

В первой строке входных данных даются числа $n$ и $k$ $(1 <= n <= 10^5, 1 <= k <= 20)$.

Во второй строке входных данных даётся массив $a$ длины $k$ $(1 <= a_i <= 10^9)$.

В следующих $n$ строк даются массивы длины $k$, где в $i$-ой содержится массив $b_i$ $(1 <= b_{ij} <= 10^9,$ где $1 <= i <= k)$.

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

В единственной строке выходных данных выведите одно число - ответ на задачу.

Примеры

Вход

3 1
2
1
2
2

Выход

4