{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003eUsoperanto is an artificial spoken language designed and regulated by Usoperanto Academy.\nThe academy is now in study to establish Strict Usoperanto, a variation of the language intended for formal documents.\n\u003c/p\u003e\n\u003cp\u003eIn Usoperanto, each word can modify at most one other word, and modifiers are always put before modifiees.\nFor example, with a noun \u003ci\u003euso\u003c/i\u003e (\"truth\") modified by an adjective \u003ci\u003emakka\u003c/i\u003e (\"total\"), people say \u003ci\u003emakka uso\u003c/i\u003e, not \u003ci\u003euso makka\u003c/i\u003e.\nOn the other hand, there have been no rules about the order among multiple words modifying the same word,\nso in case \u003ci\u003euso\u003c/i\u003e is modified by one more adjective \u003ci\u003ebeta\u003c/i\u003e (\"obvious\"),\npeople could say both \u003ci\u003emakka beta uso\u003c/i\u003e and \u003ci\u003ebeta makka uso\u003c/i\u003e.\n\u003c/p\u003e\n\u003cp\u003eIn Strict Usoperanto, the word order will be restricted according to \u003ci\u003emodification costs\u003c/i\u003e.\nWords in a phrase must be arranged so that the total modification cost is minimized.\nEach pair of a modifier and a modifiee is assigned a cost equal to the number of letters between the two words;\nthe total modification cost is the sum of the costs over all modifier-modifiee pairs in the phrase.\nFor example, the pair of \u003ci\u003emakka\u003c/i\u003e and \u003ci\u003euso\u003c/i\u003e in a phrase \u003ci\u003emakka beta uso\u003c/i\u003e has the cost of 4 for \u003ci\u003ebeta\u003c/i\u003e (four letters).\nAs the pair of \u003ci\u003ebeta\u003c/i\u003e and \u003ci\u003euso\u003c/i\u003e has no words in between and thus the cost of zero, \u003ci\u003emakka beta uso\u003c/i\u003e has the total modification cost of 4.\nSimilarly \u003ci\u003ebeta makka uso\u003c/i\u003e has the total modification cost of 5.\nApplying the \"minimum total modification cost\" rule, \u003ci\u003emakka beta uso\u003c/i\u003e is preferred to \u003ci\u003ebeta makka uso\u003c/i\u003e in Strict Usoperanto.\n\u003c/p\u003e\n\u003cp\u003eYour mission in this problem is to write a program that, given a set of words in a phrase, finds the correct word order in Strict Usoperanto and reports the total modification cost.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003eThe format of the input is as follows.\n\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cvar\u003eN\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eM\u003csub\u003e0\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003eL\u003csub\u003e0\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003e...\u003c/var\u003e\u003cbr\u003e\u003cvar\u003eM\u003csub\u003eN-1\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003eL\u003csub\u003eN-1\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\n\u003cp\u003eThe first line contains an integer\n\u003c!--\u003cvar\u003eN\u003c/var\u003e (\u003cvar\u003e1 \u0026le; N \u0026le; 160,000\u003c/var\u003e).--\u003e\n\u003cvar\u003eN\u003c/var\u003e (\u003cvar\u003e1 ≤ N ≤ 10\u003csup\u003e6\u003c/sup\u003e\u003c/var\u003e).\n\u003cvar\u003eN\u003c/var\u003e is the number of words in a phrase.\n\u003c/p\u003e\n\u003cp\u003eEach of the following \u003cvar\u003eN\u003c/var\u003e lines contains two integers\n\u003cvar\u003eM\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (\u003cvar\u003e1 ≤ M\u003csub\u003ei\u003c/sub\u003e ≤ 10\u003c/var\u003e) and\n\u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (\u003cvar\u003e-1 ≤ L\u003csub\u003ei\u003c/sub\u003e ≤ N - 1\u003c/var\u003e, \u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e ≠ i\u003c/var\u003e)\ndescribing the \u003cvar\u003ei\u003c/var\u003e-th word (\u003cvar\u003e0 ≤ i ≤ N-1\u003c/var\u003e).\n\u003cvar\u003eM\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e is the number of the letters in the word.\n\u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e specifies the modification:\n\u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e \u003d -1\u003c/var\u003e indicates it does not modify any word;\notherwise it modifies the \u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e-th word.\n\u003c/p\u003e\n\u003cp\u003eNote the first sample input below can be interpreted as the \u003ci\u003euso\u003c/i\u003e-\u003ci\u003ebeta\u003c/i\u003e-\u003ci\u003emakka\u003c/i\u003e case.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003ePrint the total modification cost.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e3\n3 -1\n4 0\n5 0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e4\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e3\n10 -1\n10 0\n10 1\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e0\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e4\n1 -1\n1 0\n1 1\n1 0\n\u003c/pre\u003e\n\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e1\n\u003c/pre\u003e\n"}}]}