{"raw_statement":[{"iden":"statement","content":"With two _Spear of Shojin_ and a _Guinsoo's Rageblade_, *Pyke* is dominating in the arena of _Teamfight Tactics_.\n\nAfter bitterly lose to the team based on Glacial and Archers of Lowie's, B21 spent days and nights to research on the mystery of the champion Pyke. He found something interesting, (_it might be a bug_) but still can bring him great advantages in TFT games.\n\nB21 found $N$ sets of attacks for Pyke. Each set consists of $A_i$ attacks. After completing set of attacks of index $i$, the attack speed of Pyke equals to minimum value between current attack speed and $B_i$ milliseconds for each attack. And to defeat Lowie, Pyke have to complete all $N$ sets of attacks. Help B21 find the minimum time Pyke complete all $N$ sets in milliseconds. Know that, at first Pyke have completed the first set of attacks.\n\nThe first line contains an integer $N$ ($1 <= N <= 10^5$).\n\nThe second line contains $N$ intergers $A_i$ ($1 <= A_i <= 10^6$).\n\nThe third line contains $N$ intergers $B_i$ ($1 <= B_i <= 10^6$).\n\nIt is guaranteed that $A_1 = 1$ and $B_n = 0$ and $A_1 < A_2 <... < A_n$ and $B_1 > B_2 >... > B_n$.\n\nPrint exactly one integer - the minimum time Pyke complete all $N$ sets in milliseconds.\n\nIn the first example, Pyke complete set of attacks of index $1, 4, 5, 2, 3$ respectively or index $1, 4, 5, 3, 2$.\n\nIn the second example, Pyke complete set of attacks of index $1, 3, 6, 2, 4, 5$ respectively or index $1, 3, 6, 2, 5, 4$, ......\n\n"},{"iden":"input","content":"The first line contains an integer $N$ ($1 <= N <= 10^5$).The second line contains $N$ intergers $A_i$ ($1 <= A_i <= 10^6$).The third line contains $N$ intergers $B_i$ ($1 <= B_i <= 10^6$).It is guaranteed that $A_1 = 1$ and $B_n = 0$ and $A_1 < A_2 <... < A_n$ and $B_1 > B_2 >... > B_n$."},{"iden":"output","content":"Print exactly one integer - the minimum time Pyke complete all $N$ sets in milliseconds."},{"iden":"examples","content":"Input5\n1 2 3 4 6\n5 4 3 1 0\nOutput26\nInput6\n1 2 3 8 9 10\n5 4 3 2 1 0\nOutput45\n"},{"iden":"note","content":"In the first example, Pyke complete set of attacks of index $1, 4, 5, 2, 3$ respectively or index $1, 4, 5, 3, 2$.In the second example, Pyke complete set of attacks of index $1, 3, 6, 2, 4, 5$ respectively or index $1, 3, 6, 2, 5, 4$, ......"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of attack sets.  \nLet $ A = (A_1, A_2, \\dots, A_N) $ be a strictly increasing sequence of integers with $ A_1 = 1 $ and $ A_i \\in [1, 10^6] $.  \nLet $ B = (B_1, B_2, \\dots, B_N) $ be a strictly decreasing sequence of integers with $ B_N = 0 $ and $ B_i \\in [1, 10^6] $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ A_1 = 1 $, $ A_1 < A_2 < \\dots < A_N $  \n3. $ B_1 > B_2 > \\dots > B_N = 0 $  \n\n**Objective**  \nPyke must complete all $ N $ attack sets in some order, starting with set 1.  \nAfter completing set $ i $, Pyke’s attack speed is capped at $ B_i $ milliseconds per attack (i.e., attack rate becomes $ \\frac{1000}{B_i} $ attacks per second).  \n\nThe time to complete a set $ i $ with $ A_i $ attacks under current speed cap $ c $ (in ms/attack) is $ A_i \\cdot c $.  \n\nThe speed cap is updated to the **minimum** of the current cap and $ B_i $ after completing set $ i $.  \n\nFind the **minimum total time** (in milliseconds) to complete all $ N $ sets, starting with set 1, and visiting each set exactly once.  \n\n**Note**: The order of sets after the first is not fixed; we may permute sets $ \\{2, 3, \\dots, N\\} $ arbitrarily.  \n\n**Objective Reformulation**  \nLet $ \\pi $ be a permutation of $ \\{1, 2, \\dots, N\\} $ with $ \\pi(1) = 1 $.  \nDefine $ c_1 = B_1 $, and for $ k = 2 $ to $ N $:  \n$ c_k = \\min(c_{k-1}, B_{\\pi(k)}) $  \n\nTotal time:  \n$$\nT(\\pi) = \\sum_{k=1}^{N} A_{\\pi(k)} \\cdot c_k\n$$  \n\nMinimize $ T(\\pi) $ over all such permutations $ \\pi $.","simple_statement":"Pyke starts with 1 attack and must complete N attack sets.  \nFor set i:  \n- It takes A_i attacks to finish.  \n- After finishing, his attack speed is capped at B_i ms per attack.  \n- He must do all sets in some order.  \n- Initial speed: after set 1, speed = B_1.  \n- B_n = 0, meaning final speed is instant.  \n- A_i increases, B_i decreases.  \nFind minimum total time (in ms) to complete all sets.","has_page_source":false}