JOI 상점에는 \(N\)개의 상품이 있으며, 상품에는 1부터 \(N\)까지 번호가 붙어 있다. 상품 \(i\) (\(1 \le i \le N\))의 정가는 \(A_i\)이다. JOI 상점의 인터넷 쇼핑에서는 상품을 살 때 한 종류의 쿠폰을 0장 이상 원하는 만큼 사용할 수 있다. JOI 상점의 쿠폰은 \(Q\)종류가 있으며, 쿠폰 종류에는 1부터 \(Q\)까지 번호가 붙어 있다. 종류 \(j\) (\(1 \le j \le Q\))의 쿠폰을 \(k\)장 (\(k \ge 0\)) 사용했을 때의 효과는 다음과 같다.
각 쿠폰 종류에 대응하여 \(Q\)개의 질문을 생각할 수 있다. \(j\)번째 질문은 다음과 같다.
상품과 쿠폰 정보가 주어졌을 때, 각 질문에 대한 답을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(Q\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(C_1\) \(D_1\)
\(\vdots\)
\(C_Q\) \(D_Q\)
제약 조건
- \(1 \le N \le 300{,}000\)
- \(1 \le Q \le 300{,}000\)
- \(1 \le A_i \le 10^9\) (\(1 \le i \le N\))
- \(1 \le C_j \le 10^9\) (\(1 \le j \le Q\))
- \(1 \le D_j \le 10^9\) (\(1 \le j \le Q\))
- 입력되는 값은 모두 정수이다.
부분문제
- (6점) \(N = 1\), \(Q \le 3{,}000\)
- (3점) \(N \le 100\), \(Q \le 100\), \(A_i \le 100\) (\(1 \le i \le N\))
- (8점) \(N \le 3{,}000\), \(Q \le 3{,}000\), \(D_j = 1\) (\(1 \le j \le Q\))
- (22점) \(N \le 3{,}000\), \(Q \le 3{,}000\)
- (15점) \(D_j = 1\) (\(1 \le j \le Q\))
- (18점) \(A_i \le 1{,}000{,}000\) (\(1 \le i \le N\))
- (28점) 추가 제약 조건 없음
다음 형식으로 출력한다.
\(Q\)줄 출력한다. \(j\)번째 줄 (\(1 \le j \le Q\))에는 \(j\)번째 질문에 대한 답을 출력한다.
1번째 질문에서, 종류 1의 쿠폰을 1장 쓰면 각 상품 가격은 3, 5, 0이 되고, 합계 금액은 \(3 + 5 + 0 + 12 \times 1 = 20\)이다. 20보다 작은 합계를 만들 수 없으므로 20을 출력한다.
2번째 질문에서, 종류 2의 쿠폰을 4장 쓰면 각 상품 가격은 0, 2, 0이 되고, 합계 금액은 \(0 + 2 + 0 + 3 \times 4 = 14\)이다. 14보다 작은 합계를 만들 수 없으므로 14를 출력한다.
3번째 질문에서, 종류 3의 쿠폰을 2장 쓰면 각 상품 가격은 0, 2, 0이 되고, 합계 금액은 \(0 + 2 + 0 + 3 \times 2 = 8\)이다. 8보다 작은 합계를 만들 수 없으므로 8을 출력한다.
4번째 질문에서, 종류 4의 쿠폰을 0장 쓰면 각 상품 가격은 8, 10, 3이 되고, 합계 금액은 \(8 + 10 + 3 + 100 \times 0 = 21\)이다. 21보다 작은 합계를 만들 수 없으므로 21을 출력한다.