The ministry, which issues licenses to work \textbf{N} officials (including ministers), and: \begin{itemize} \item Each officer (except the Minister) has a superior; \item Each officer has a \textbf{0} to \textbf{4} subordinate officials; \item Chief of my chief, not my chief; \item Slave of my slave, not my slave. \end{itemize} License signed by the Minister. To have the signature of any officer or minister, you need to bribe him to Dachi, after having received the signature of one of his subordinates, if any. What is the minimum amount sufficient to obtain a license? \includegraphics{https://static.e-olymp.com/content/5a/5a744b8968964b17bb5a3bdb4a4bae79c658313a.jpg} \InputFile The first line of the number \textbf{N} -- the number of officials in the ministry. Next comes the \textbf{N} lines. In the \textbf{і}-th row (\textbf{і }=\textbf{ 1..N}) recorded data on the \textbf{і}-th clerk in the following format: \textbf{D\[і\]} - sum of bribes, \textbf{K\[і\]} -- the amount and number of his subordinates. The minister has the number one. All numbers are natural and do not exceed \textbf{100}. \OutputFile The answer to the problem.