{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eMany centuries ago Martians switched to using huge robots\r\nfor military operations. During the current Moon conquest\r\ncampaign, all of the Martian army is located at the headquarters\r\non Mars, and each person is controlling the actions of his \r\nrobot. There is a strict hierarchy in the Martian army: each\r\nperson excepting the general (there is only one general in the \r\narmy) has a direct commander. According to the army regulations, \r\ncommunication is allowed only between a commander and his direct \r\nsubordinate. The communication is carried out via the headquarters\r\nlocal network. At the headquarters, each military person has \r\nhis own computer, and computers are numbered from 1 to \u003ci\u003eN\u003c/i\u003e, \r\nwhere \u003ci\u003eN\u003c/i\u003e is the size of the Martian army. It is a tradition \r\nthat a subordinate\u0027s computer has number that is greater than the \r\nnumber of his commander\u0027s computer. Each military person,\r\nin addition to the number of his computer, is characterized by \r\nhis reliability. This is a real number; the owner of the computer\r\n\u003ci\u003ei\u003c/i\u003e has reliability \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e. The general has \r\nreliability 1, and soldiers (soldiers and only they have no \r\nsubordinates) have reliability 0.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe traffic in the headquarters network is not free\r\nfor the military. For every megabyte of traffic between\r\nthe \u003ci\u003ei\u003c/i\u003eth computer and the computer of the commander\r\nof the \u003ci\u003ei\u003c/i\u003eth computer\u0027s owner, the central Martian\r\nprovider demands \u003ci\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e Martian dollars in payment.\r\nThe complication is that the volume of traffic between any \r\ntwo headquarters computers is a state secret, and is unknown \r\neven to the provider. Every month the provider sends a bill, and \r\nthe military write there the traffic (a whole number of \r\nmegabytes) themselves. Let a commander and his subordinate\r\nhave computers with numbers \u003ci\u003ei\u003c/i\u003e and \u003ci\u003ek\u003c/i\u003e respectively.\r\nAccording to the contract with the provider, the traffic \r\nbetween the computers \u003ci\u003ei\u003c/i\u003e and \u003ci\u003ek\u003c/i\u003e must be\r\nnot less than \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e–\u003ci\u003eA\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e. \r\nIn the beginning of every month, the provider\u0027s representatives\r\nknow the hierarchy in the Martian army and costs of a megabyte of \r\ntraffic, but they don\u0027t know the numbers \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \r\nexcept for the general and soldiers, and of course they don\u0027t \r\nknow beforehand the amounts of traffic that the military will \r\nwrite in the bill. It is interesting to know the guaranteed\r\namount of money that the provider will receive from the military.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains the size of the army\r\n2 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100000. \r\nEach of the next \u003ci\u003eN\u003c/i\u003e–1 lines contains\r\nintegers \u003ci\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e,\r\nwhich are the number of the computer of the commander\r\nof the \u003ci\u003ei\u003c/i\u003eth computer\u0027s owner and the cost of a megabyte \r\nof traffic between the computers \u003ci\u003ei\u003c/i\u003e and \r\n\u003ci\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\r\n(1 ≤ \u003ci\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u0026lt; \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e,\r\n0 ≤ \u003ci\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 1000).\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the minimal guaranteed amount of payment to the provider in Martian dollars.\r\nThis amount must be a real number given with exactly two decimal digits.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n1 10\r\n2 5\r\n2 3\r\n3 1\r\n3 2\r\n3 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8.00\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}