{"problem":{"name":"Insertion Sort","description":{"content":"There are $N$ people, who are given ID numbers $1$ through $N$, standing in a row from left to right. Initially, the ID number of the $i$\\-th person from the left is $P_i$. Your objective is to rearra","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc201_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ people, who are given ID numbers $1$ through $N$, standing in a row from left to right. Initially, the ID number of the $i$\\-th person from the left is $P_i$.\nYour objective is to rearrange the people in ascending order of the ID number from left to right, by repeatedly doing the three kinds of operations below. You can do these operations any number of times (possibly zero) in any order.\n\n*   Choose an integer $i\\ (1 \\leq i \\leq N)$, pay the cost $A_i$, and move Person $i$ (the person with the ID number $i$) to any position of your choice.\n*   Choose an integer $i\\ (1 \\leq i \\leq N)$, pay the cost $B_i$, and move Person $i$ to the left end of the row.\n*   Choose an integer $i\\ (1 \\leq i \\leq N)$, pay the cost $C_i$, and move Person $i$ to the right end of the row.\n\nMinimize the total cost you pay before achieving the objective.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq P_i \\leq N$\n*   $1 \\leq A_i,B_i,C_i \\leq 10^9$\n*   $P_i \\neq P_j\\ (i \\neq j)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_N$ $B_N$ $C_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc201_f","tags":[],"sample_group":[["3\n3 1 2\n9 3 5\n8 6 4\n9 4 6","6\n\nYou can rearrange the people in ascending order of the ID number by paying the cost $C_3=6$ to move Person $3$ to the right end.\nThere is no way to rearrange the people that costs less, so the answer is $6$."],["6\n2 6 5 3 4 1\n10 8 16\n30 2 10\n10 17 8\n11 27 22\n8 6 5\n15 29 2","15\n\nThe following sequence of operations minimizes the total cost:\n\n*   pay the cost $B_1=8$ to move Person $1$ to the left end;\n*   pay the cost $C_5=5$ to move Person $5$ to the right end;\n*   pay the cost $C_6=2$ to move Person $6$ to the right end."],["9\n3 8 4 7 6 9 1 5 2\n7976 3696 9706\n768 8807 8521\n1133 8683 7120\n1189 3331 2259\n900 7451 1159\n6126 2639 7107\n5540 8253 2891\n8417 4220 9091\n8732 1417 1540","15865"],["12\n11 9 1 12 2 7 3 5 10 4 6 8\n3960 3158 9029\n6521 6597 7581\n5688 2299 2123\n4946 4298 9122\n394 4350 9142\n3098 7151 2039\n8525 3758 6155\n6970 3658 9353\n9780 1778 3608\n6065 5562 923\n9701 5524 6482\n9395 6016 705","20637"]],"created_at":"2026-03-03 11:01:14"}}