Flipping Range solution codeforces- You are given an array aa of nn integers and a set BB of mm positive integers such that 1≤bi≤⌊n2⌋1≤bi≤⌊n2⌋ for 1≤i≤m1≤i≤m, where bibi is the ii-th element of BB. You can make the following operation on aa: Select some xx such that xx appears in BB. Select an interval from array aa of size xx and multiply by −1−1 every element in the interval. Formally, select ll and rr such that 1≤l≤r≤n1≤l≤r≤n and r−l+1=xr−l+1=x, then assign ai:=−aiai:=−ai for every ii such that l≤i≤rl≤i≤r. Consider the following example, let a=[0,6,−2,1,−4,5]a=[0,6,−2,1,−4,5] and B={1,2}B={1,2}: [0,6,−2,−1,4,5][0,6,−2,−1,4,5] is obtained after choosing size 22 and l=4l=4, r=5r=5. [0,6,2,−1,4,5][0,6,2,−1,4,5] is obtained after choosing size 11 and l=3l=3, r=3r=3. Find the maximum ∑i=1nai∑i=1nai you can get after applying such operation any number of times (possibly zero).

Flipping Range solution codeforces

You are given an array aa of nn integers and a set BB of mm positive integers such that 1≤bi≤⌊n2⌋1≤bi≤⌊n2⌋ for 1≤i≤m1≤i≤m, where bibi is the ii-th element of BB.

You can make the following operation on aa:

  1. Select some xx such that xx appears in BB.
  2. Select an interval from array aa of size xx and multiply by −1−1 every element in the interval. Formally, select ll and rr such that 1≤l≤r≤n1≤l≤r≤n and r−l+1=xr−l+1=x, then assign ai:=−aiai:=−ai for every ii such that l≤i≤rl≤i≤r.

Consider the following example, let a=[0,6,−2,1,−4,5]a=[0,6,−2,1,−4,5] and B={1,2}B={1,2}:

  1. [0,6,−2,−1,4,5][0,6,−2,−1,4,5] is obtained after choosing size 22 and l=4l=4, r=5r=5.
  2. [0,6,2,−1,4,5][0,6,2,−1,4,5] is obtained after choosing size 11 and l=3l=3, r=3r=3.

Find the maximum ∑i=1nai∑i=1nai you can get after applying such operation any number of times (possibly zero).

Input Flipping Range solution codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1051≤t≤105) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers nn and mm (2≤n≤1062≤n≤106, 1≤m≤⌊n2⌋1≤m≤⌊n2⌋) — the number of elements of aa and BB respectively.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109).

The third line of each test case contains mm distinct positive integers b1,b2,…,bmb1,b2,…,bm (1≤bi≤⌊n2⌋1≤bi≤⌊n2⌋) — the elements in the set BB.

It’s guaranteed that the sum of nn over all test cases does not exceed 106106.

Output Flipping Range solution codeforces

For each test case print a single integer — the maximum possible sum of all aiai after applying such operation any number of times.

Example

input

Copy
3
6 2
0 6 -2 1 -4 5
1 2
7 1
1 -1 1 -1 1 -1 1
2
5 1
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000
1

output Flipping Range solution codeforces

Copy
18
5
5000000000
Note

In the first test, you can apply the operation x=1x=1, l=3l=3, r=3r=3, and the operation x=1x=1, l=5l=5, r=5r=5, then the array becomes [0,6,2,1,4,5][0,6,2,1,4,5].

In the second test, you can apply the operation x=2x=2, l=2l=2, r=3r=3, and the array becomes [1,1,−1,−1,1,−1,1][1,1,−1,−1,1,−1,1], then apply the operation x=2x=2, l=3l=3, r=4r=4, and the array becomes [1,1,1,1,1,−1,1][1,1,1,1,1,−1,1]. There is no way to achieve a sum bigger than 55.

Leave a Comment

Your email address will not be published.