В этом году для помощи в подготовке олимпиады IQ ПФО жюри решило пригласить Рудольфа, раз уж он является главным героем всех задач. Рудольф с радостью согласился и не только придумал несколько задач о себе, но и предложил членам жюри для интереса сделать ставки на результаты решения задач.
Сначала каждый из N членов жюри вносит в банк S биткойнов, формируя призовой фонд. Затем каждый член жюри делает прогноз, записывая, сколько команд, по его мнению, решат первую, вторую, ..., последнюю задачу. В олимпиаде участвуют M команд, а пакет включает K задач.
Погрешностью прогноза по одной задаче называется модуль разности между прогнозируемым и фактическим количествами команд, решивших эту задачу. Общей погрешностью прогноза называется его суммарная погрешность по всем задачам. Призовой фонд получает тот член жюри, прогноз которого имеет наименьшую общую погрешность. Если победителей несколько, то они делят призовой фонд поровну (с округлением вниз).
Помогите членам жюри определить наиболее точный прогноз и выяснить, сколько биткойнов получит его автор.
Первая строка содержит целые числа N, S, M и K (1 ≤ N ≤ 1000, 1 ≤ S ≤ 105, 1 ≤ M ≤ 1000, 1 ≤ K ≤ 1000) — соответственно количество членов жюри, размер ставки каждого из членов жюри, количество команд-участников олимпиады и количество задач.
Следующие N строк описывают прогнозы членов жюри. Каждая из них содержит последовательность Si, состоящую из строчных латинских букв и цифр, а также K целых чисел Pij (1 ≤ |Si| ≤ 20, 0 ≤ Pij ≤ M) — соответственно имя члена жюри и количество команд, которым, по его мнению, удастся решить 1-ю, 2-ю, ..., K-ю задачу. Все имена членов жюри различны.
Следующие M строк описывают результаты олимпиады. Каждая из них содержит последовательность Ti, состоящую из строчных латинских букв и цифр, а также K разделённых пробелами символов Rij (1 ≤ |Ti| ≤ 20, _+_, _-_) — соответственно название команды и её результат по 1-й, 2-й, ..., K-й задаче. Символ _+_ означает, что команда решила задачу, символ _-_ означает, что команда не решила задачу. Все названия команд различны.
Выведите одно целое число — выигрыш автора наиболее точного прогноза.
## Входные Данные
Первая строка содержит целые числа N, S, M и K (1 ≤ N ≤ 1000, 1 ≤ S ≤ 105, 1 ≤ M ≤ 1000, 1 ≤ K ≤ 1000) — соответственно количество членов жюри, размер ставки каждого из членов жюри, количество команд-участников олимпиады и количество задач.Следующие N строк описывают прогнозы членов жюри. Каждая из них содержит последовательность Si, состоящую из строчных латинских букв и цифр, а также K целых чисел Pij (1 ≤ |Si| ≤ 20, 0 ≤ Pij ≤ M) — соответственно имя члена жюри и количество команд, которым, по его мнению, удастся решить 1-ю, 2-ю, ..., K-ю задачу. Все имена членов жюри различны.Следующие M строк описывают результаты олимпиады. Каждая из них содержит последовательность Ti, состоящую из строчных латинских букв и цифр, а также K разделённых пробелами символов Rij (1 ≤ |Ti| ≤ 20, _+_, _-_) — соответственно название команды и её результат по 1-й, 2-й, ..., K-й задаче. Символ _+_ означает, что команда решила задачу, символ _-_ означает, что команда не решила задачу. Все названия команд различны.
## Выходные Данные
Выведите одно целое число — выигрыш автора наиболее точного прогноза.
## Примеры
Входные данные2 10 3 2rudolph 1 2linsierra 3 1team1 + -team2 + -team3 + +Выходные данные20Входные данные4 3 3 4rudolph 3 3 1 3linsierra 2 2 1 3zhrv 2 1 0 3javarthur 1 1 1 3welovegena + + - +welovepetya + - - +welovefood - - + +Выходные данные4
[samples]
**Definitions**
Let $ N, S, M, K \in \mathbb{Z}^+ $:
- $ N $: number of jury members,
- $ S $: bet amount per jury member,
- $ M $: number of teams,
- $ K $: number of problems.
Let $ J = \{j_1, \dots, j_N\} $ be the set of jury members, each with name $ s_j \in \Sigma^* $ and prediction vector $ P_j = (p_{j1}, p_{j2}, \dots, p_{jK}) \in \{0, 1, \dots, M\}^K $.
Let $ T = \{t_1, \dots, t_M\} $ be the set of teams. For each team $ t_i $, let $ R_i = (r_{i1}, r_{i2}, \dots, r_{iK}) \in \{+, -\}^K $ be its result vector.
Define the **actual count** for problem $ \ell \in \{1, \dots, K\} $:
$$
a_\ell = \left| \left\{ i \in \{1, \dots, M\} \mid r_{i\ell} = + \right\} \right|
$$
Define the **absolute error** of jury member $ j $ on problem $ \ell $:
$$
e_{j\ell} = |p_{j\ell} - a_\ell|
$$
Define the **total error** of jury member $ j $:
$$
E_j = \sum_{\ell=1}^K e_{j\ell}
$$
**Constraints**
1. $ 1 \le N \le 1000 $
2. $ 1 \le S \le 10^5 $
3. $ 1 \le M \le 1000 $
4. $ 1 \le K \le 1000 $
5. $ 0 \le p_{j\ell} \le M $ for all $ j, \ell $
6. $ |s_j| \le 20 $, $ |t_i| \le 20 $
**Objective**
Let $ E_{\min} = \min_{j \in J} E_j $.
Let $ W = \left\{ j \in J \mid E_j = E_{\min} \right\} $ be the set of winners.
The prize pool is $ N \cdot S $.
Each winner receives $ \left\lfloor \frac{N \cdot S}{|W|} \right\rfloor $ bitcoins.
Output: $ \left\lfloor \frac{N \cdot S}{|W|} \right\rfloor $