The factory has $$$N-1$$$ workshops for the production of various details. Each workshop has exactly one outgoing conveyor on which details are transferred to some other workshop. At the same time, each workshop is capable of receiving (and then sending through its conveyor) any number of details sent by other workshops to it.
It's almost time for assembly! Recently, yet one workshop with the number $$$N$$$ for the final assembly of products has been opened at the factory. Now it is necessary to build one or more additional conveyors so that any detail can eventually reach the workshop $$$N$$$.
Building conveyors is costly. For each workshop, the cost of building one additional conveyor outgoing from it is known (note that the destination workshop does not affect the cost). Determine the minimum sum required for building new conveyors, as well as which conveyors should be built. It is allowed to build several additional conveyors for any of the $$$N$$$ workshops.
The first line of the input data contains an integer $$$N$$$ ($$$3 \le N \le 2 \cdot 10^5$$$).
The second line contains $$${N-1}$$$ natural numbers $$$e_1$$$, $$$e_2$$$, $$$\dots$$$, $$$e_{N-1}$$$ ($$$e_i \le {N-1}$$$) — the numbers of the workshops where the conveyors arrive, outgoing from workshops with numbers $$$1$$$, $$$2$$$, $$$\dots$$$, $$${N-1}$$$, respectively.
The third line contains $$$N$$$ integers $$$c_1$$$, $$$c_2$$$, $$$\dots$$$, $$$c_N$$$ ($$$1 \le c_i \le 10^9$$$) — the costs of building one additional conveyor, transferring parts from workshops with numbers $$$1, 2, \dots, N$$$ respectively.
The first line of the output should contain two numbers $$$S$$$ and $$$K$$$ — the total cost of building new conveyors and their quantity.
Next, print $$$K$$$ lines containing two natural numbers $$$a_j$$$ and $$$b_j$$$, where $$$a_j$$$ is the number of the workshop where the $$$j$$$th new conveyor comes from, and $$$b_j$$$ is the number of the workshop where this conveyor arrives.
If there are multiple correct answers, output any.
42 3 114 13 12 11
12 1 3 4
52 1 4 31 1 1 1 1
2 2 2 3 4 5
Illustration for the first example:
