현재 거의 모든 이동통신사는 각 개인이 자신에게 가장 적합한 요금제를 선택할 수 있도록 광범위한 요금제를 보유하고 있습니다. 불행하게도 어느 요금제가 가장 최선일지 선택하는 것은 매우 어려운 경우가 많습니다.
이동통신사 중 하나의 경우 각 요금표는 가입비 \(c_i\)(루블 단위), 최소 충전 시간 단위 \(t_i\)(초 단위), 최소 충전 시간 단위 비용 \(p_i\)(코페이카 단위)의 세 가지 숫자로 표시됩니다. \(1\)루블은 \(100\)코페이카와 같습니다. 한 달간 총 통화 비용은 가입비와 발신 통화 비용의 합계입니다. \(i\)번째 요금제 사용 시 발신 통화 비용은 다음과 같이 계산됩니다:
통화 시간이 \(T\)초인 경우, \(T \lt t_i\)이면 호출 비용은 \(0\)입니다. 그렇지 않은 경우 호출 비용은 \(k \cdot p_i\)와 같습니다. 여기서 \(k\)는 \(k \cdot t_i \ge T\)인 최소 정수입니다.
한 달 동안 가입자의 발신 통화는 총 \(m\)건이며 각각 \(d_1, ..., d_m\)(초)입니다. 이러한 통화의 총 비용이 최소화되는 요금제를 찾아주세요.
입력
첫 번째 줄에는 두 개의 정수 \(n\)(요금제의 개수)과 \(m\)(발신 통화 수)이 포함됩니다.(\(1 \le n, m \le 100\)). 다음 \(n\)개의 행 각각은 하나의 요금제를 나타내며 공백으로 구분된 세 개의 정수 \(c_i(0 \le c_i \le 100), t_i(1 \le t_i \le 3600), p_i(0 \le p_i \le 1000)\)로 구성됩니다.
마지막 줄에는 \(m\)개의 정수 \(d_1, ..., d_m\)(1에서 \(m\)까지의 모든 i에 대해 \(1 \le d_i \le 3600\))이 포함됩니다.
출력
해당 달에 가입자에게 발신 전화의 총 비용이 최소화되는 요금제 번호를 하나 출력합니다. 요금제 번호는 입력 순서와 같습니다.(\(1\)부터 \(n\)까지의 정수) 해당하는 요금제개 여러 개라면 그 중 하나를 출력하세요.
iktk 3년 전 6
문제
현재 거의 모든 이동통신사는 각 개인이 자신에게 가장 적합한 요금제를 선택할 수 있도록 광범위한 요금제를 보유하고 있습니다. 불행하게도 어느 요금제가 가장 최선일지 선택하는 것은 매우 어려운 경우가 많습니다.
이동통신사 중 하나의 경우 각 요금표는 가입비 \(c_i\)(루블 단위), 최소 충전 시간 단위 \(t_i\)(초 단위), 최소 충전 시간 단위 비용 \(p_i\)(코페이카 단위)의 세 가지 숫자로 표시됩니다. \(1\)루블은 \(100\)코페이카와 같습니다. 한 달간 총 통화 비용은 가입비와 발신 통화 비용의 합계입니다. \(i\)번째 요금제 사용 시 발신 통화 비용은 다음과 같이 계산됩니다:
통화 시간이 \(T\)초인 경우, \(T \lt t_i\)이면 호출 비용은 \(0\)입니다. 그렇지 않은 경우 호출 비용은 \(k \cdot p_i\)와 같습니다. 여기서 \(k\)는 \(k \cdot t_i \ge T\)인 최소 정수입니다.
한 달 동안 가입자의 발신 통화는 총 \(m\)건이며 각각 \(d_1, ..., d_m\)(초)입니다. 이러한 통화의 총 비용이 최소화되는 요금제를 찾아주세요.
입력
첫 번째 줄에는 두 개의 정수 \(n\)(요금제의 개수)과 \(m\)(발신 통화 수)이 포함됩니다.(\(1 \le n, m \le 100\)). 다음 \(n\)개의 행 각각은 하나의 요금제를 나타내며 공백으로 구분된 세 개의 정수 \(c_i(0 \le c_i \le 100), t_i(1 \le t_i \le 3600), p_i(0 \le p_i \le 1000)\)로 구성됩니다.
마지막 줄에는 \(m\)개의 정수 \(d_1, ..., d_m\)(1에서 \(m\)까지의 모든 i에 대해 \(1 \le d_i \le 3600\))이 포함됩니다.
출력
해당 달에 가입자에게 발신 전화의 총 비용이 최소화되는 요금제 번호를 하나 출력합니다. 요금제 번호는 입력 순서와 같습니다.(\(1\)부터 \(n\)까지의 정수) 해당하는 요금제개 여러 개라면 그 중 하나를 출력하세요.