There are *n* balls. They are arranged in a row. Each ball has a color (for convenience an integer) and an integer value. The color of the *i*-th ball is *c*<sub class="lower-index">*i*</sub> and the value of the *i*-th ball is *v*<sub class="lower-index">*i*</sub>.

Squirrel Liss chooses some balls and makes a new sequence without changing the relative order of the balls. She wants to maximize the value of this sequence.

The value of the sequence is defined as the sum of following values for each ball (where *a* and *b* are given constants):
 -  If the ball is not in the beginning of the sequence and the color of the ball is same as previous ball's color, add (the value of the ball)  ×  *a*. -  Otherwise, add (the value of the ball)  ×  *b*. 
You are given *q* queries. Each query contains two integers *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub>. For each query find the maximal value of the sequence she can make when *a* = *a*<sub class="lower-index">*i*</sub> and *b* = *b*<sub class="lower-index">*i*</sub>.

Note that the new sequence can be empty, and the value of an empty sequence is defined as zero.
The first line contains two integers *n* and *q* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>; 1 ≤ *q* ≤ 500). The second line contains *n* integers: *v*<sub class="lower-index">1</sub>, *v*<sub class="lower-index">2</sub>, ..., *v*<sub class="lower-index">*n*</sub> (|*v*<sub class="lower-index">*i*</sub>| ≤ 10<sup class="upper-index">5</sup>). The third line contains *n* integers: *c*<sub class="lower-index">1</sub>, *c*<sub class="lower-index">2</sub>, ..., *c*<sub class="lower-index">*n*</sub> (1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ *n*).

The following *q* lines contain the values of the constants *a* and *b* for queries. The *i*-th of these lines contains two integers *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> (|*a*<sub class="lower-index">*i*</sub>|, |*b*<sub class="lower-index">*i*</sub>| ≤ 10<sup class="upper-index">5</sup>).

In each line integers are separated by single spaces.
def  choosing_balls():
    n,q = [int(x) for x in input().split()]
    v = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    c.insert(0,0)
    v.insert(0,0)
   
    for _ in range(q):
        a,b = [int(x) for x in input().split()]
        dp = [-1000000000000000] * (n+5)
        dp[0]=0
        maxc=0
        second_maxc=0
        for i in range(1,n+1):
            ans = max(dp[c[i]]+ v[i]*a,dp[second_maxc]+v[i]*b)
            if(maxc != c[i]):
                ans = max(ans,dp[maxc] + v[i]*b)
                if(ans > dp[maxc]):
                    second_maxc=maxc
                    maxc=c[i]
                elif(ans > dp[second_maxc]):
                    second_maxc=c[i]
            dp[c[i]] = max(dp[c[i]],ans)
        print(dp[maxc])

choosing_balls()