1538: White

作为一个带有洞穴的岛屿的主人，当你发现地下石油能够带来巨大财富时非常开心。当然，一个洞穴能够存储的石油越多越好。你的洞穴的有效容积不是很容易计算，因为它的形状相当奇怪（看下图）。感谢上帝，这是退化为1维的。

上图中，黑色区域是可存储的石油。

       注意，洞穴的上边界（ceiling）布满了线。你不能保证它们是完好无损的，因此你需要保证在任何一处石油都不能超过上边界。你可以在任何一处灌油，可能造成若干个池塘。记住，石油是液体，它总会使得它的重力势能最小，也就是说，它会在水平方向上朝任何一处跑，无论何时，只要有可能，就会倾盆而下，同时遵循连通器原理。现在，就由你来计算储水的最大面积。

       输入的第一行包含一个正整数t（t ≤ 10），代表测试数据的组数。

       对于每组测试数据，第一行一个正整数n（n≤10⁶），代表洞穴的宽度。第二行n个整数p₁，p₂……p_n，第三行n个整数s₁，s₂……s_n，均用空格隔开。p_i和q_i满足0 ≤ p_i < q≤1000，代表第i段的下界（floor）和上界。

       对于每组测试数据，输出一行，一个整数，代表能够存储的最大面积。

1
15
6 6 7 5 5 5 5 5 5 1 1 3 3 2 2
10 10 10 11 6 8 7 10 10 7 6 4 7 11 11

14