D. Genius
bitmasks; dp; graphs; number theory
Please note the non-standard memory limit.There are \(n\) problems numbered with integers from \(1\) to \(n\). \(i\)-th problem has the complexity \(c_i = 2^i\), tag \(tag_i\) and score \(s_i\).After solving the problem \(i\) it's allowed to solve problem \(j\) if and only if \(\text{IQ} < |c_i - c_j|\) and \(tag_i \neq tag_j\). After solving it your \(\text{IQ}\) changes and becomes \(\text{IQ} = |c_i - c_j|\) and you gain \(|s_i - s_j|\) points.Any problem can be the first. You can solve problems in any order and as many times as you want.Initially your \(\text{IQ} = 0\). Find the maximum number of points that can be earned.
The first line contains a single integer \(t\) \((1 \le t \le 100)\) — the number of test cases. The first line of each test case contains an integer \(n\) \((1 \le n \le 5000)\) — the number of problems.The second line of each test case contains \(n\) integers \(tag_1, tag_2, \ldots, tag_n\) \((1 \le tag_i \le n)\) — tags of the problems.The third line of each test case contains \(n\) integers \(s_1, s_2, \ldots, s_n\) \((1 \le s_i \le 10^9)\) — scores of the problems.It's guaranteed that sum of \(n\) over all test cases does not exceed \(5000\).
For each test case print a single integer — the maximum number of points that can be earned.
In the first test case optimal sequence of solving problems is as follows: \(1 \rightarrow 2\), after that total score is \(5\) and \(\text{IQ} = 2\) \(2 \rightarrow 3\), after that total score is \(10\) and \(\text{IQ} = 4\) \(3 \rightarrow 1\), after that total score is \(20\) and \(\text{IQ} = 6\) \(1 \rightarrow 4\), after that total score is \(35\) and \(\text{IQ} = 14\) In the second test case optimal sequence of solving problems is as follows: \(1 \rightarrow 2\), after that total score is \(5\) and \(\text{IQ} = 2\) \(2 \rightarrow 3\), after that total score is \(10\) and \(\text{IQ} = 4\) \(3 \rightarrow 4\), after that total score is \(15\) and \(\text{IQ} = 8\) \(4 \rightarrow 1\), after that total score is \(35\) and \(\text{IQ} = 14\) In the third test case optimal sequence of solving problems is as follows: \(1 \rightarrow 3\), after that total score is \(17\) and \(\text{IQ} = 6\) \(3 \rightarrow 4\), after that total score is \(35\) and \(\text{IQ} = 8\) \(4 \rightarrow 2\), after that total score is \(42\) and \(\text{IQ} = 12\)