Müasir dövrdə demək olar ki, hər bir mobil əlaqə operatoru geniş tariflər yığımına malikdir. Bu, hər kəsə özünə uyğun tarifi seçməyə imkan verir. Təəssüf ki, bu seçimi insanın özünün hesablaması çox çətindir.

Mobil operatorlarının birində hər tarif 3 ədəd ilə xarakterizə olunur: abonent ödənişi ci (manatla verilir), minimal tarifə malik vaxt vahidi ti (saniyə ilə verilir), minimal tarifə malik vaxt vahidinin qiyməti pi (qəpiklə verilir, bir manat 100 qəpikdir). Ay ərzində zənglərin ümumi qiyməti abonent ödənişindən və hər bir çıxış zənginin qiymətindən ibarətdir. İ tarifindən istifadə etməklə bir zəngin qiyməti belə hesablanır: Tutaq ki, danışıq vaxtı T saniyəyə bərabərdir. Əgər T < ti olarsa, zəngin qiyməti 0-a bərabərdir. Əks halda zəngin qiyməti k-nın pi-ə hasilinə bərabərdir, burada k, k · ti ≥ T şərtini ödəyən ən kiçik tam ədəddir.

Tariflərin izahı və ay ərzində abonentin çıxış zənglərinin statistikası verilmişdir: m - zənglərin sayı, d1, ..., dm (saniyə ilə) zənglərin müddətidir. Elə tarif tapın ki, bu zənglərin ümumi qiyməti minimal olsun.

Giriş verilənlər

Birinci sətir n və m tam ədədlərindən ibarət olmalıdır, belə ki, n tariflərin sayı (1 ≤ n), m abonentlərin çıxış zənglərinin sayıdır (m ≤ 100). Hər bir növbəti n sətir bir tarifi göstərir və 3 tam ədəddən ibarətdir: ci (0 ≤ ci ≤ 100), ti (1 ≤ ti ≤ 3600), pi (0 ≤ pi ≤ 1000).

Axırıncı sətir isə m tam ədəddən ibarətdir: d1, ..., dm (1 ≤ di ≤ 3600 1-dən m-ə qədər olan bütün i-lər üçün).

Çıxış verilənlər

Elə tarif nömrəsini verin ki, ondan istifadə etdikdə verilən ay ərzində abonentitn çıxış zənglərinin ümumi qiyməti minimal olsun. Tariflər girişdə verildiyi sıra ilə, 1-dən n**-ə **kimi tam ədədlərlə nömrələnir. Əgər bir neçə belə tarif varsa, onlardan istənilən birinin nömrəsini verin.