怪物与咒语

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

第 $i$ 个怪物在关卡开始后的第 $k_i$ 秒出现，拥有 $h_i$ 点生命值。保证 $h_i\le k_i$，且怪物出现时刻严格递增。

Monocarp 可以在第 $1,2,3,\ldots$ 秒施放咒语。伤害按以下规则决定：

• 如果上一秒没有施法，本次伤害为 $1$；
• 如果上一秒施法造成了 $x$ 点伤害，本次可以选择造成 $1$ 或 $x+1$ 点伤害。

一次施法消耗与伤害值相同的法力，法力不会恢复。要击杀第 $i$ 个怪物，Monocarp 必须在第 $k_i$ 秒施法，且伤害不少于 $h_i$。没有怪物出现时也可以施法。

求击杀所有怪物所需的最少法力。

输入格式

第一行包含一个整数 $t$（$1\le t\le10^4$）。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le100$）。

第二行包含 $n$ 个严格递增的整数 $k_i$（$1\le k_i\le10^9$），表示出现时刻。

第三行包含 $n$ 个整数 $h_i$（$1\le h_i\le k_i$），表示生命值。

所有测试用例的 $n$ 之和不超过 $10^4$。

输出格式

对每个测试用例输出一行最少法力。

样例输入 1

3
1
6
4
2
4 5
2 2
3
5 7 9
2 1 2

样例输出 1

10
6
7

数据范围