시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 164 | 42 | 40 | 25.641% |
В настоящее время практически каждый оператор сотовой связи имеет обширный набор тарифов, которые позволяют каждому человеку выбрать наиболее подходящий для себя. К сожалению, зачастую осуществить этот выбор вручную очень тяжело.
У одного из сотовых операторов каждый тариф характеризуется тремя числами: абонентная плата ci (задается в рублях), минимальная тарифицируемая единица времени ti (задается в секундах), стоимость минимальной тарифицируемой единицы времени pi (задается в копейках, в одном рубле 100 копеек). Суммарная стоимость вызовов за месяц складывается из абонентной платы и стоимостей каждого из исходящих вызовов. Стоимость вызова при использовании i-ого тарифа вычисляется следующим образом: пусть время разговора равно T секунд. Если T < ti, то стоимость вызова равна нулю. Иначе стоимость вызова равна произведению k на pi, где k — минимальное целое число, такое что k·ti ≥ T.
Задано описание тарифов и статистика исходящих вызовов абонента в течение месяца — их число m и длительности d1, ..., dm в секундах. Необходимо найти тариф, при котором суммарная стоимость этих вызовов была бы минимальной.
Первая строка содержит два целых числа n и m — соответственно количество тарифов и исходящих вызовов абонента (1 ≤ n, m ≤ 100). Каждая из последующих n строк описывает один тариф и содержит три целых числа: ci (0 ≤ ci ≤ 100), ti (1 ≤ ti ≤ 3600), pi (0 ≤ pi ≤ 1000).
Последняя строка содержит m целых чисел d1, ..., dm (1 ≤ di ≤ 3600 для всех i от 1 до m).
Выведите одно число — номер тарифа, при использовании которого суммарная стоимость исходящих вызовов абонента за рассматриваемый месяц минимальна. Тарифы нумеруются целыми числами от 1 до n в том порядке, в котором они заданы во входном файле. Если таких тарифов несколько, выведите номер любого из них.
2 1 100 60 100 51 10 100 600
1