Balanced Subarray with Maximum Weighted Sum

You are given a sequence of positive integers (a_1,a_2,\dots,a_n) and an integer sequence (b_1,b_2,\dots,b_n). You are also given (q) queries. In each query, you are given two integers (x) and (y). With these, you define a new sequence (c_1,c_2,\dots,c_n) as follows: [ c_i = \begin{cases} 1, & \text{if } a_i = x,\ -1, & \text{if } a_i = y,\ 0, & \text{otherwise.} \end{cases} ] It is guaranteed that in the sequence (c) there is at least one occurrence of (1) and at least one occurrence of (-1).

Your task is: for each query, find an interval ([l,r]) (with (1 \le l \le r \le n)) satisfying

1. (\displaystyle \sum_{i=l}^r c_i = 0), and
2. The interval contains at least one index (i) for which (c_i \neq 0) (i.e. not all (c_i) in ([l,r]) are zero).

Among all such intervals, you want to maximize the following weighted sum: [ \sum_{i=l}^r b_i \times [c_i \neq 0], ] where ([P]) is the indicator function that is (1) if the predicate (P) is true and (0) otherwise.

Output the maximum weighted sum for each query.

Note: The contributions (b_i) of indices where (a_i \notin {x,y}) are ignored in the sum, although such indices may be included in the interval.

inputFormat

The input consists of multiple lines:

• The first line contains two integers (n) and (q) ( (1 \le n, q \le \text{small to moderate constraints})), representing the length of sequences and the number of queries.
• The second line contains (n) space-separated positive integers (a_1, a_2, \dots, a_n).
• The third line contains (n) space-separated integers (b_1, b_2, \dots, b_n).
• The following (q) lines each contain two integers (x) and (y). It is guaranteed that for each query the constructed sequence (c) contains at least one (1) and at least one (-1).

outputFormat

For each query, output a single line containing one integer — the maximum weighted sum (\sum_{i=l}^r b_i\times [c_i\neq 0]) over all intervals ([l,r]) which satisfy (\sum_{i=l}^r c_i=0) and contain at least one index with (c_i \neq 0).

sample

5 2
1 2 1 2 3
10 -5 20 30 40
1 2
1 3

55
60