CF1497D Genius

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. $ 1 \rightarrow 2 $ , after that total score is $ 5 $ and $ \text{IQ} = 2 $ 2. $ 2 \rightarrow 3 $ , after that total score is $ 10 $ and $ \text{IQ} = 4 $ 3. $ 3 \rightarrow 1 $ , after that total score is $ 20 $ and $ \text{IQ} = 6 $ 4. $ 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. $ 1 \rightarrow 2 $ , after that total score is $ 5 $ and $ \text{IQ} = 2 $ 2. $ 2 \rightarrow 3 $ , after that total score is $ 10 $ and $ \text{IQ} = 4 $ 3. $ 3 \rightarrow 4 $ , after that total score is $ 15 $ and $ \text{IQ} = 8 $ 4. $ 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. $ 1 \rightarrow 3 $ , after that total score is $ 17 $ and $ \text{IQ} = 6 $ 2. $ 3 \rightarrow 4 $ , after that total score is $ 35 $ and $ \text{IQ} = 8 $ 3. $ 4 \rightarrow 2 $ , after that total score is $ 42 $ and $ \text{IQ} = 12 $