Чилден придумал легендарную историю и пытается продать свою подделку — ожерелье с «Wu» семье Касура. Но мистер Касура пытается разузнать всю правду из истории Чилдена. Поэтому он задаст несколько вопросов Чилдену о его так называемом «личном сокровище».
Это «личное сокровище» представляет собой мультимножество \(S\) из \(m\) «01-строк».
«01-строка» — строка, которая состоит из \(n\) символов «0» и «1». Например, если \(n=4\), то «0110», «0000», и «1110» являются «01-строками», но «00110» (в ней \(5\) символов, а не \(4\)) и «zero» (неразрешенные символы) не являются.
Обратите внимание, что мультимножество \(S\) может содержать одинаковые элементы.
Иногда мистер Касура будет давать «01-строку» \(t\) и спрашивать Чилдена количество строк \(s\) в мультимножестве \(S\) таких, что «Wu»-стоимость пары «01-строк» \((s, t)\) не больше чем \(k\).
Миссис Касура и мистер Касура считают, что, если \(s_i = t_i\) (\(1\leq i\leq n\)), то «Wu»-стоимость пары символов равна \(w_i\), иначе — \(0\). «Wu»-стоимость пары «01-строк» равняется сумме всех «Wu»-стоимостей пар их символов. Заметьте, что длина каждой «01-строк» равняется \(n\).
Например, если \(w=[4, 5, 3, 6]\), «Wu» от («1001», «1100») равно \(7\), потому что эти строки имеют одинаковые символы только в первой и третьей позициях, значит \(w_1+w_3=4+3=7\).
Вам нужно помочь Чилдену ответить на запросы мистера Касуры. То есть найти количество строк в мультимножестве \(S\) таких, что «Wu»-стоимость пары не больше \(k\).
Выходные данные
Для каждого запроса выведите ответ на него.
Примечание
В первом примере мы имеем:
«Wu» от («01», «00») равно \(40\).
«Wu» от («10», «00») равно \(20\).
«Wu» от («11», «00») равно \(0\).
«Wu» от («01», «11») равно \(20\).
«Wu» от («10», «11») равно \(40\).
«Wu» от («11», «11») равно \(60\).
В первом запросе пары («11», «00») и («10», «00») удовлетворяют условие поскольку «Wu» не больше \(20\).
Во втором примере все пары удовлетворяют условие.
В третьем примере пары («01», «11») и («01», «11») удовлетворяют условие. Обратите внимание, что поскольку строка «01» встречается два раза в мультимножестве, то ответ \(2\), а не \(1\).
В четвертом примере, поскольку \(k\) увеличилось, то пара («10», «11») тоже удовлетворяет условие.
В пятом примере, поскольку \(k\) увеличилось, то пара («11», «11») тоже удовлетворяет условие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4 5
40 20
01
01
10
11
00 20
00 40
11 20
11 40
11 60
|
2
4
2
3
4
|
|
2
|
1 2 4
100
0
1
0 0
0 100
1 0
1 100
|
1
2
1
2
|