{"raw_statement":[{"iden":"statement","content":"Consider the following game about removing N straight line segments on the plane. The segments are numbered from 1 to N. The i-th segment connects points (0, i) and (1, pi), where the numbers p1, p2, ..., pN are a permutation of numbers from 1 to N. Your are also given N positive integers v1, v2, ..., vN. On each step, you can select any segment i which is not removed yet, pay vi dollars, and then remove the i-th segment and all segments intersecting with it. Note that you MUST remove all segments which intersect with i-th segment.\n\nThe purpose of this game is to remove all segments while spending the minimum possible sum of dollars. Please answer how much you need to spend when you play the game with best strategy.\n\nThe input consists of three lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. The third line consists of N integer v1, v2, ..., vN.\n\nOutput only one number indicating the minimum possible sum of dollars required to remove all segments.\n\n"},{"iden":"input","content":"The input consists of three lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. The third line consists of N integer v1, v2, ..., vN.  1 ≤ N ≤ 105   is a permutation of 1, 2, ..., N  1 ≤ vi ≤ 2 × 104 "},{"iden":"output","content":"Output only one number indicating the minimum possible sum of dollars required to remove all segments."},{"iden":"examples","content":"Input42 1 4 31 2 3 4Output4Input41 2 3 41 2 3 4Output10"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $.  \nLet $ \\mathbf{p} = (p_1, p_2, \\dots, p_N) $ be a permutation of $ \\{1, 2, \\dots, N\\} $.  \nLet $ \\mathbf{v} = (v_1, v_2, \\dots, v_N) \\in \\mathbb{R}^N_{>0} $.  \nFor each $ i \\in \\{1, \\dots, N\\} $, define segment $ s_i $ as the line segment connecting $ (0, i) $ and $ (1, p_i) $.\n\n**Constraints**  \nSegments $ s_i $ and $ s_j $ (with $ i \\ne j $) intersect if and only if $ (i - j)(p_i - p_j) < 0 $.\n\n**Objective**  \nFind the minimum total cost to remove all segments, where selecting segment $ i $ costs $ v_i $ and removes $ i $ and all segments intersecting $ s_i $.  \nFormally, find:  \n$$\n\\min_{\\text{covering sets } C} \\sum_{i \\in C} v_i\n$$  \nwhere $ C \\subseteq \\{1, \\dots, N\\} $ is a set such that every segment $ j \\in \\{1, \\dots, N\\} $ is either in $ C $ or intersects some segment in $ C $.","simple_statement":"You have N line segments on a plane. Each segment i connects (0, i) to (1, p[i]), where p is a permutation of 1 to N. Each segment i has a cost v[i]. When you pick a segment, you pay its cost and remove it plus all segments that cross it. Find the minimum total cost to remove all segments.","has_page_source":false}