22188번 - Тарифы 스페셜 저지다국어

문제

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

У одного из сотовых операторов каждый тариф характеризуется тремя числами: абонентная плата c_i (задается в рублях), минимальная тарифицируемая единица времени t_i (задается в секундах), стоимость минимальной тарифицируемой единицы времени p_i (задается в копейках, в одном рубле 100 копеек). Суммарная стоимость вызовов за месяц складывается из абонентной платы и стоимостей каждого из исходящих вызовов. Стоимость вызова при использовании i-ого тарифа вычисляется следующим образом: пусть время разговора равно T секунд. Если T < t_i, то стоимость вызова равна нулю. Иначе стоимость вызова равна произведению k на p_i, где k — минимальное целое число, такое что k·t_i ≥ T.

Задано описание тарифов и статистика исходящих вызовов абонента в течение месяца — их число m и длительности d₁, ..., d_m в секундах. Необходимо найти тариф, при котором суммарная стоимость этих вызовов была бы минимальной.

입력

Первая строка содержит два целых числа n и m — соответственно количество тарифов и исходящих вызовов абонента (1 ≤ n, m ≤ 100). Каждая из последующих n строк описывает один тариф и содержит три целых числа: c_i (0 ≤ c_i ≤ 100), t_i (1 ≤ t_i ≤ 3600), p_i (0 ≤ p_i ≤ 1000).

Последняя строка содержит m целых чисел d₁, ..., d_m (1 ≤ d_i ≤ 3600 для всех i от 1 до m).

출력

Выведите одно число — номер тарифа, при использовании которого суммарная стоимость исходящих вызовов абонента за рассматриваемый месяц минимальна. Тарифы нумеруются целыми числами от 1 до n в том порядке, в котором они заданы во входном файле. Если таких тарифов несколько, выведите номер любого из них.

제한

힌트