Тарифи#2497

Тарифи

1 секунда

122,486 мегабайта

Легка

У наш час майже кожен мобільний оператор пропонує широкий вибір тарифів, що дозволяє кожному обрати найбільш підходящий варіант. Проте часто зробити цей вибір вручну досить складно.

Кожен тариф мобільного оператора характеризується трьома числами: абонентська плата $c_{i}$ c_i (у національній валюті), мінімальна тарифікована одиниця часу $t_{i}$ t_i (у секундах) та вартість однієї мінімальної одиниці часу $p_{i}$ p_i (у найменших грошових одиницях, де одна основна грошова одиниця дорівнює $100$ найменших). Загальна вартість дзвінків за місяць складається з абонентської плати та вартості кожного вихідного дзвінка. Вартість дзвінка за $i$ -м тарифом розраховується так: нехай тривалість дзвінка становить $T$ секунд. Якщо $T < t_{i}$ T < t_i, то вартість дзвінка дорівнює нулю. Інакше вартість дзвінка дорівнює добутку $k$ на $p_{i}$ p_i, де $k$ — найменше ціле число таке, що $k \cdot t_{i} \geq T$ k \cdot t_i \geq T.

Опис тарифів та статистика вихідних дзвінків за місяць наведені нижче: $m$ — кількість дзвінків, а їхні тривалості $d_{1}, \dots, d_{m}$ d_1, \ldots, d_m у секундах. Знайдіть той тариф, для якого загальна вартість цих дзвінків буде мінімальною.

Вхідні дані

У першому рядку містяться два цілі числа $n$ та $m$ — кількість тарифів і кількість вихідних дзвінків ( $1 \leq n, m \leq 100$ 1 \leq n, m \leq 100).

Кожен із наступних $n$ рядків описує один тариф і містить три цілі числа: $c_{i}$ c_i ( $0 \leq c_{i} \leq 100$ 0 \leq c_i \leq 100), $t_{i}$ t_i ( $1 \leq t_{i} \leq 3600$ 1 \leq t_i \leq 3600), $p_{i}$ p_i ( $0 \leq p_{i} \leq 1000$ 0 \leq p_i \leq 1000).

Останній рядок містить $m$ цілих чисел $d_{1}, \dots, d_{m}$ d_1, \ldots, d_m ( $1 \leq d_{i} \leq 3600$ 1 \leq d_i \leq 3600 для всіх $i$ від $1$ до $m$ ).

Вихідні дані

Виведіть номер тарифу, для якого загальна вартість вихідних дзвінків протягом заданого місяця буде мінімальною. Тарифи нумеруються від $1$ до $n$ у тому ж порядку, в якому подані у вхідних даних. Якщо таких тарифів декілька, виведіть будь-який з них.

Приклади

Приклад 1