Description

小祥從 F1 退役之後決定轉戰摩托車比賽,加入 MotoGP。MotoGP 是由施巨砲 (GP) 舉辦的摩托車賽事,每場比賽都有許多人參加,但是因為小祥跟施巨砲太強了,所以今年度的 MotoGP 儼然成為了小祥跟施巨砲的一對一對決。

MotoGP 中,有 N 個可選的比賽賽道,從左到右為第 1 個到第 N 個。小祥跟施巨砲各自熟悉不同的賽道,因此對於第 i 個賽道來說,小祥的技能值為 Ai,施巨砲的技能值為 Bi。在一場 MotoGP 的賽事中,會選取一段區間 [i,j] ,並用第 i 個到第 j 個賽道進行比賽。對於小祥來說,他想要讓他與施巨砲的技能值差距越大;同時,因為他覺得他的體力比施巨砲好(每多一場比賽,他就比施巨砲好 K 個單位的體能),他也想要讓比賽的賽道數量越多越好。因此,對於一段區間 [i,j] 來說,小祥對它的好感度為 maxivjAvmaxivjBv+K(ji+1)

接下來會舉行連續 Q 天的賽事,每天只有第 L 到第 R 條賽道是能比賽的,比賽委員會會在這些賽道內選擇一段連續的區間 [i,j] 比賽 (LijR)。小祥靠著關係賄賂了比賽委員會,讓他可以選擇要選哪些賽道比賽。請幫他寫一個程式,計算對於每天的比賽,他的最大好感度為何(注意好感度可能為負數)。

Input Format

第一行有兩個整數 N,K,意義如題目所述
第二行有 N 個正整數 A1,,AN,代表小祥對賽道的技能值
第三行有 N 個正整數 B1,,BN,代表施巨砲對賽道的技能值
第四行有一個正整數 Q ,代表詢問數量
接下來的 Q 行中,每行有兩個正整數 Li,Ri ,代表當天有比賽的賽道

對於所有測試資料:

  • 1N,Q100000
  • 0K108
  • 1Ai,Bi1013

Output Format

請輸出 Q 行,每行輸出一個整數,代表第 i 天的最大好感度。

Sample Input 1

5 2
8 4 5 3 9
2 6 1 2 10
4
1 5
1 3
2 3
4 5

Sample Output 1

10
8
6
3

Sample Input 2

10 5
88 16 42 15 94 65 3 9 98 4
50 3 95 36 25 59 35 77 1 69
6
1 10
5 9
2 4
5 10
9 10
2 10

Sample Output 2

102
102
18
102
102
102

Hints

範例測資 1 解釋:

對於第 1 天,小祥可以選擇 [1,4],此時好感度為 86+2(41+1)=10
對於第 2 天,小祥可以選擇 [1,3],此時好感度為 86+2(31+1)=8
對於第 3 天,小祥可以選擇 [3,3],此時好感度為 51+2(33+1)=6
對於第 4 天,小祥可以選擇 [4,4],此時好感度為 32+2(44+1)=3

Problem Source

2024 MotoGP 系列賽可以在 YouTube SPOTV Asia 免費收看喔~

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~6 N,Q100 7
3 0~11 N2000 14
4 3, 8, 12~17 K=0 15
5 18~26 Q=1L1=1R1=N 26
6 0~39 無特別限制 38

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4500 1048576 65536 1 2 3 6
1 4500 1048576 65536 1 2 3 6
2 4500 1048576 65536 2 3 6
3 4500 1048576 65536 2 3 4 6
4 4500 1048576 65536 2 3 6
5 4500 1048576 65536 2 3 6
6 4500 1048576 65536 2 3 6
7 4500 1048576 65536 3 6
8 4500 1048576 65536 3 4 6
9 4500 1048576 65536 3 6
10 4500 1048576 65536 3 6
11 4500 1048576 65536 3 6
12 4500 1048576 65536 4 6
13 4500 1048576 65536 4 6
14 4500 1048576 65536 4 6
15 4500 1048576 65536 4 6
16 4500 1048576 65536 4 6
17 4500 1048576 65536 4 6
18 4500 1048576 65536 5 6
19 4500 1048576 65536 5 6
20 4500 1048576 65536 5 6
21 4500 1048576 65536 5 6
22 4500 1048576 65536 5 6
23 4500 1048576 65536 5 6
24 4500 1048576 65536 5 6
25 4500 1048576 65536 5 6
26 4500 1048576 65536 5 6
27 4500 1048576 65536 6
28 4500 1048576 65536 6
29 4500 1048576 65536 6
30 4500 1048576 65536 6
31 4500 1048576 65536 6
32 4500 1048576 65536 6
33 4500 1048576 65536 6
34 4500 1048576 65536 6
35 4500 1048576 65536 6
36 4500 1048576 65536 6
37 4500 1048576 65536 6
38 4500 1048576 65536 6
39 4500 1048576 65536 6