binary search

data structures

dp

flows

greedy

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Two Characters, Two Colors

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou are given a string consisting of characters 0 and/or 1. You have to paint every character of this string into one of two colors, red or blue.

If you paint the $$$i$$$-th character red, you get $$$r_i$$$ coins. If you paint it blue, you get $$$b_i$$$ coins.

After coloring the string, you remove every blue character from it, and count the number of inversions in the resulting string (i. e. the number of pairs of characters such that the left character in the pair is 1, and the right character in the pair is 0). For each inversion, you have to pay $$$1$$$ coin.

What is the maximum number of coins you can earn?

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of four lines:

- the first line contains one integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the length of the string;
- the second line contains $$$s$$$ — a string of $$$n$$$ characters, where each character is either 0 or 1;
- the third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^{12}$$$);
- the fourth line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$).

Additional constraint on the input: the sum of values of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, print one integer — the maximum number of coins you can earn.

Example

Input

4701000106 6 6 7 7 6 63 3 5 4 7 6 75101119 8 5 7 54 4 7 8 41001000000007 7 6 5 2 2 5 3 8 38 6 9 6 6 8 9 7 7 98010100008 7 7 7 8 7 7 84 4 4 2 1 4 4 4

Output

43 36 76 52

Note

Explanations for the test cases for the example (blue characters are underlined, red ones are not):

- $$$0100\underline{0}1\underline{0}$$$;
- $$$10\underline{11}1$$$;
- $$$\underline{0}1\underline{00000000}$$$;
- $$$0\underline{1}010000$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 09:37:05 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|