Kevin去砍树
题号：NC255612
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一片繁茂的树林
一片繁茂的树林

有 n 棵树木排成一排，第 i 棵树木的位置为 i，高度为 h_i，价值为 w_i。

氧气少年现在需要砍伐树木，他遵守下面的规则进行砍伐，直到无法砍伐为止。

  •  氧气少年可以从任意一棵树木开始砍伐。
  •  从砍伐第二棵树开始，氧气少年只能选择上一棵被砍伐的树木的左侧或右侧的紧邻的未砍伐的树木进行砍伐。
  •  从砍伐第二棵树开始，氧气少年砍伐的树木的高度必须严格小于上一棵被砍伐的树木的高度。
  •  每当砍伐掉一棵树木时，氧气少年将获得这棵树木的价值。

阅读样例解释可以帮助理解上述过程。

请求出氧气少年能获得的最大价值总和。

输入描述:

第一行包含一个整数 T(1\leq T \leq 10^5)，表示测试用例的组数。

对于每组测试用例：

第一行包含一个整数 n(1\leq n\leq 2\cdot 10^5)，表示树木的数量。

第二行包含 n 个整数 h_1\dots h_n(1\leq h_i\leq n)，表示每棵树木的高度。

第三行包含 n 个整数 w_1\dots w_n(1\leq w_i\leq 10^9)，表示每棵树木的价值。

保证对于所有的测试用例，n 的总和不超过 2\cdot 10^5。

输出描述:

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。
示例1

输入

复制 
2
3
2 3 2
10 10 10
5
1 1 4 3 4
20 90 66 90 88

输出

复制 
20
246

说明

对于第一组测试用例：

可以先砍伐编号为 2 的树木，获得 10 收益，再砍伐编号为 1 的树木，获得 10 收益，总收益为 20；
也可以先砍伐编号为 2 的树木，获得 10 收益，再砍伐编号为 3 的树木，获得 10 收益，总收益为 20。

对于第二组测试用例：

可以先砍伐编号为 3 的树木，获得 66 收益，再砍伐编号为 4 的树木，获得 90 收益，再砍伐编号为 2 的树木，获得 90 收益，总收益为 246。