요금제

요즘 거의 모든 이동통신사는 다양한 요금제를 제공하므로 누구나 자신에게 맞는 요금제를 고를 수 있다. 그러나 이런 선택을 직접 하기는 매우 어려운 경우가 많다.

어느 이동통신사의 요금제는 세 정수로 정의된다. 월 기본료 ci(단위는 루블), 최소 과금 단위 시간 ti(단위는 초), 최소 과금 단위 시간의 가격 pi(단위는 코펙, 1루블은 100코펙)이다. 한 달 동안의 총 통화 비용은 기본료와 발신 통화 각각의 비용을 합한 값이다. i번째 요금제에서 통화 비용은 다음과 같이 계산한다. 통화 시간이 T초라고 하자. T < ti이면 통화 비용은 0이다. 그렇지 않으면 통화 비용은 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 ≤ i ≤ m인 모든 i에 대해 1 ≤ di ≤ 3600).

해당 월의 발신 통화 총 비용이 최소가 되는 요금제의 번호를 출력한다. 요금제는 입력 파일에 주어진 순서대로 1부터 n까지의 정수로 번호가 매겨진다. 그러한 요금제가 여러 개라면 아무 번호나 하나 출력한다.