창고 출고 청구서

문제

물류 창고의 백엔드는 출고 기록을 입력된 순서대로 보관한다. 각 기록에는 할인 전 작업 요금과 해당 작업에 적용할 할인율이 저장되어 있다. 운영자는 연속한 출고 기록을 묶어 청구서를 미리 계산하려 한다. 같은 출고 기록이 여러 청구서에 포함될 수 있으며, 청구서 계산은 원본 기록이나 다른 청구서에 영향을 주지 않는다. 출고 기록 i의 할인 전 작업 요금을 A_i원, 할인율을 D_i퍼센트라고 한다. 이 기록의 할인 후 요금은 A_i에 (100-D_i)를 곱한 뒤 100으로 나눈 몫이다. 소수 부분은 기록마다 버린다. 여러 기록의 할인 전 요금을 먼저 합하거나, 기록별 할인액을 따로 버리는 방식으로 계산하지 않는다. 할인 후 요금은 0원이 될 수도 있다. 각 청구서 요청에는 시작 기록 번호 L, 끝 기록 번호 R, 정액 쿠폰 금액 C가 주어진다. 먼저 L번부터 R번까지 양 끝을 포함한 모든 기록의 할인 후 요금을 합한다. 다음으로 합계에서 쿠폰 금액을 뺀다. 그 결과가 음수이면 0원으로 바꾼다. 이렇게 얻은 금액이 과세 대상 금액이다. 세금은 과세 대상 금액을 10으로 나눈 몫이며, 최종 청구 금액은 과세 대상 금액과 세금의 합이다. 쿠폰은 청구서마다 독립적으로 적용된다. 사용하지 못한 쿠폰 금액은 이월하거나 환불하지 않으며, 세금을 계산한 뒤 쿠폰을 적용해서도 안 된다. 모든 계산은 원 단위 정수로 수행한다. 요청이 주어진 순서대로 각 청구서의 최종 청구 금액을 구해야 한다. 기록을 선택하거나 청구서 사이의 우선순위를 정하는 과정은 없다.

입력

첫째 줄에 출고 기록 수 N과 청구서 요청 수 Q가 주어진다. 다음 N개 줄의 i번째 줄에 A_i와 D_i가 주어진다. 다음 Q개 줄에 L R C가 주어진다.
모든 입력값은 정수이다. 1≤N≤20,000, 1≤Q≤8,000, 0≤A_i≤999, 0≤D_i≤100, 1≤L≤R≤N, 0≤C≤20,000,000이다. 기록 번호는 1부터 시작한다.

출력

각 요청의 최종 청구 금액을 요청 순서대로 한 줄에 하나씩 출력한다. 쿠폰 적용 후 과세 대상 금액이 0원이면 0을 출력한다.

4 3
100 10
205 20
80 0
99 50
1 4 0
2 3 44
4 4 100

421
220
0

3 3
1 100
19 0
19 50
1 1 0
2 3 0
1 3 8

0
30
22

출처: Devin.KR 자체 제작