Chef and Tetris

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef loves Tetris. He keeps on playing Tetris all the time. Today Chef's mother wanted to him play something else and brought an array for her son. That is why Chef now decided to play Tetris with arrays. Here are the rules of the game:
 Chef has an array A consisting of N positive integers. This is a base array.
 Chef has an array B consisting of N positive integers. He placed this array directly above the array A. Imagine that array B is falling on array A, such that number B_{i} is directly above the number A_{i} initially.
 If element B_{i} falls on A_{i}, A_{i} gets increased by B_{i}.
 Each element B_{i} can be dropped by Chef on either A_{i1}, A_{i} or A_{i+1}.
 Chef can't drop element out of array (for example he can't drop B_{0} on A_{1}).
 Chef wants all the elements of array A to become equal, and looking for the biggest possible value he can get.
Please help Chef in enjoying the game!!
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains a single integer N denoting the number of elements in both arrays.
 The second line contains N spaceseparated integers B_{1}, B_{2}, ..., B_{N} denoting the elements of the falling array.
 The third line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the elements of the base array.
Output
 For each test case, output a single line containing a biggest integer Chef can get for all elements of array A or 1 if it is impossible.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 10^4
 1 ≤ A_{i} ≤ 10^{6}
 1 ≤ B_{i} ≤ 10^{6}
Subtasks
 Subtask N ≤ 15. Points: 30
 Subtask N ≤ 10^{4}. Points: 70
Example
Input: 3 1 10 20 4 15 7 10 10 6 14 21 1 3 1 100 3 1 2 3 Output: 30 21 1
Explanation
Example case 1. The only option in first example is to make 10 fall on 20. As we have only one element condition of equality is satisfied.
Example case 2. Here Chef makes 15 fall on 6, 7 fall on 14, an then both elements with value 10 should fall on 1. Then all elements will become 21.
Example case 3. There is no way for Chef to make all elements of a base array equal.
Author:  berezin 
Tester:  mugurelionut 
Editorial  http://discuss.codechef.com/problems/CHEFTET 
Tags  berezin, july16, simple, simplemath 
Date Added:  16102015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions