Излом инерции для периода велопроката

Городской велопрокат ежемесячно строит несколько вариантов группировки станций. Для каждого периода и каждого числа групп сохранена инерция модели.

В первой таблице приведено число завершённых поездок по периодам. Значение NA означает, что число поездок за этот период пока не поступило. Сначала выбирается период с наибольшим известным числом завершённых поездок. Периоды со значением NA не участвуют в этом выборе.

Во второй таблице для каждого периода приведены инерции для всех значений числа групп от 1 до m. Для выбранного периода пусть I_k — инерция при k группах. Изломом для каждого k от 2 до m-1 называется величина C_k = I_{k-1} - 2·I_k + I_{k+1}. Требуется вывести такое k, для которого C_k максимально. При равенстве максимальных значений излома выводится меньшее значение k. Если несколько периодов имеют одинаковое наибольшее известное число поездок, выбирается тот из них, который раньше записан в первой таблице.

Все периоды из первой таблицы имеют ровно по одной записи инерции для каждого значения k от 1 до m; пропусков во второй таблице нет.

Формат ввода

В первой строке даны два целых числа p и q — число строк в таблице периодов и число строк в таблице инерций.

В следующих p строках записаны идентификатор периода period_id и число завершённых поездок completed_trips. Вместо числа поездок может быть записано NA.

В следующих q строках записаны идентификатор периода period_id, целое число k и целая инерция inertia. Строки второй таблицы могут идти в произвольном порядке.

Число значений k для каждого периода одинаково и равно m = q / p.

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

Выведите одно целое число — выбранное значение k.

Ограничения

1 ≤ p ≤ 100.

3 ≤ m ≤ 20, q = p · m, p + q ≤ 2000.

Идентификатор period_id состоит из латинских букв, цифр и символа -, его длина от 1 до 12. Идентификаторы периодов в первой таблице различны.

completed_trips равно NA или целому числу от 0 до 10^7. Хотя бы в одной строке первой таблицы число поездок не равно NA.

1 ≤ k ≤ m.

0 ≤ inertia ≤ 10^12. Инерции одного периода не возрастают при увеличении k.

Ответ является целым числом, округление не выполняется.