Tariffs#2497
Nowadays, almost every mobile operator offers a wide range of tariffs, allowing everyone to choose the most suitable option. However, it is often quite difficult to make this choice manually.
Each tariff of a mobile operator is characterized by three numbers: the subscription fee c_i (given in the local currency), the minimal billed time unit t_i (in seconds), and the cost of one minimal time unit p_i (in the smallest currency unit, where one main currency unit equals smallest units). The total cost of calls per month consists of the subscription fee and the cost of each outgoing call. The cost of a call when using the -th tariff is calculated as follows: let the call last seconds. If T < t_i, then the cost of the call is zero. Otherwise, the cost of the call is equal to the product of and p_i, where is the smallest integer such that k \cdot t_i \geq T.
The description of the tariffs and the statistics of outgoing calls for the month are given: — the number of calls, and their durations d_1, \ldots, d_m in seconds. Find the tariff for which the total cost of these calls is minimal.
The first line contains two integers and — the number of tariffs and the number of outgoing calls (1 \leq n, m \leq 100).
Each of the next lines describes one tariff and contains three integers: c_i (0 \leq c_i \leq 100), t_i (1 \leq t_i \leq 3600), p_i (0 \leq p_i \leq 1000).
The last line contains integers d_1, \ldots, d_m (1 \leq d_i \leq 3600 for all from to ).
Print the number of the tariff for which the total cost of outgoing calls during the given month is minimal. The tariffs are numbered from to in the order they are given in the input. If there are several such tariffs, print any one of them.
Example 1