관측 데이터 전송 요금 정산

문제

한 날씨 관측소는 매일 관측 자료를 외부 저장소로 전송하며, 전송 요금을 기간별로 정산한다. 1번부터 N번까지의 날마다 하루 단가 p_i(원)와 그날의 전송량 a_i(단위)가 정해져 있다. 하루의 요금은 p_i × a_i 원이다. 정산 기간은 l일부터 r일까지(양 끝 포함)이며, 한 번의 정산은 다음 순서로 계산한다. 첫째, 기간에 속한 모든 날의 하루 요금을 더하고 기본요금 500원을 더한 금액을 총액 G라 한다. 둘째, G가 100000 이상이면 G의 10%를, G가 50000 이상 100000 미만이면 G의 5%를 할인액으로 한다. G가 50000 미만이면 할인은 없다. 할인액은 원 미만을 버린다. 셋째, G에서 할인액을 뺀 금액을 S라 한다. 넷째, S의 10%를 부가세로 더하며, 부가세는 원 미만을 버린다. 최종 청구액은 S에 부가세를 더한 금액이다. 정산 요청이 Q개 주어질 때, 각 요청의 최종 청구액을 구하는 프로그램을 작성하라. 모든 금액은 정수이며 각 요청은 서로 독립적으로 계산한다.

입력

첫 줄에 N과 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 200000) 둘째 줄에 p_1 ... p_N이 주어진다. (1 ≤ p_i ≤ 1000) 셋째 줄에 a_1 ... a_N이 주어진다. (0 ≤ a_i ≤ 1000) 다음 Q개의 줄에 각각 l과 r이 공백으로 구분되어 주어진다. (1 ≤ l ≤ r ≤ N) 입력 전체의 길이는 400KB 이하이다.

출력

요청마다 최종 청구액을 한 줄에 하나씩 입력 순서대로 출력한다.

5 4
100 200 300 400 500
100 200 0 300 400
1 5
2 3
1 2
3 3

366795
44550
52772
550

1 1
1
0
1 1

550

출처: Devin.KR 자체 제작