Вкусы, покрывающие половину выручки

Киоск с мороженым хранит продажи отдельно от каталога вкусов. В первой таблице каждая строка содержит число проданных порций некоторого вкуса. Один и тот же вкус может встречаться в таблице продаж много раз.

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

Пусть выручки вкусов, которые встретились в таблице продаж, отсортированы по невозрастанию: \(r_1, r_2, \ldots, r_q\). Полная выручка равна \(S = r_1 + r_2 + \ldots + r_q\). Требуется найти минимальное число \(k\), для которого \[ r_1 + r_2 + \ldots + r_k \geq \frac{S}{2}. \] То есть нужно определить, сколько самых прибыльных вкусов покрывают не менее половины всей выручки киоска.

При равенстве выручек вкусы располагаются в лексикографическом порядке их кодов.

Формат ввода

В первой строке даны два целых числа n и m — число строк в таблице продаж и число строк в каталоге соответственно.

Следующие n строк содержат таблицу продаж. В каждой строке записаны код вкуса flavor_code и целое число portions — количество проданных порций в этой строке.

Следующие m строк содержат таблицу каталога. В каждой строке записаны код вкуса flavor_code и целое число price — цена одной порции в рублях.

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

Формат вывода

Выведите одно целое число k.

Дробная часть отсутствует, выводится целое число без округления.

Ограничения

• 1 ≤ n, 1 ≤ m;
• n + m ≤ 2000;
• код вкуса состоит из строчной латинской буквы, за которой следуют не более 11 строчных латинских букв или цифр;
• 1 ≤ portions ≤ 10000;
• 10 ≤ price ≤ 1000;
• коды вкусов в каталоге не повторяются;
• все количества порций и цены положительны, поэтому полная выручка положительна.