B"LuoTianyi is watching the anime Made in Abyss. She finds that making a Cartridge is interesting. To describe the process of making a Cartridge more clearly, she abstracts the original problem and gives you the following problem. You are given a tree T consisting of n vertices. Each vertex has values a_i and b_i and each edge has values c_j and d_j . Now you are aim to build a tree T' as follows: Let A be the minimum of values a_i in T' and C be the minimum of values c_i in T' . Let B be the sum of b_i in T' and D be the sum of values d_i in T' . Let min(A, C) cdot (B + D) be the cost of T' . You need to find the maximum possible cost of T' . The first line contains one integer n ( 3 <= n <= 2 cdot 10^5 ) -- the number of vertices in the tree T . The second line contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= 2 cdot 10^5 ), where the i -th integer represents the a_i value of the i -th vertex. The third line contains n integers b_1, b_2, ldots, b_n ( 1 <= b_i <= 2 cdot 10^5 ), where the i -th integer represents the b_i value of the i -th vertex. Then n-1 lines follow, the j -th of them contains four integers x_j,y_j,c_j,d_j ( 1 <= x_j,y_j <= n,1 <= c_j,d_j <= 2 cdot 10^5 ) representing the edge (x_j,y_j) and its values c_j and d_j respectively. It's guaranteed that edges form a tree. Print a single integer -- the maximum possible cost of T' . The tree from the first example is shown in the statement. The tree from the second example is shown below: A = 1, B = 18, C = 1, D = 17 , so the cost is min(1,1) cdot (18 + 17) = 35 . "...