ICPC Company has $$$N$$$ employees, with employee $$$1$$$ being the boss of the company. Each of the employees numbered $$$2$$$ through $$$N$$$ has a direct supervisor $$$s_i$$$, where $$$1 \leq s_i \lt i$$$. For employee $$$i$$$, all employees $$$s_i, s_{s_i}, \ldots, 1$$$ are considered to be supervisors of employee $$$i$$$.
Now, ICPC Company has a major project that requires sending some employees on a business trip. It is known that selecting the $$$i$$$-th employee will bring a profit of $$$p_i$$$ million dollars (if this value is negative, it means sending that employee on the trip will incur a loss).
However, selecting employees for the trip is not as simple as just choosing those with positive profits. Each employee also has a capability value $$$a_i$$$, where all capability values form a permutation of $$$1$$$ to $$$N$$$. For each employee $$$i$$$ sent on the business trip, if any of their supervisors is not sent, employee $$$i$$$ will need to handle that supervisor's tasks. But if there exists an unsent supervisor's capability value is higher than theirs, employee $$$i$$$ will feel pressure and cause a loss of $$$c_i$$$ million dollars, no matter how many unsent supervisors with higher capability value there are.
Additionally, there is another way losses can occur: for every $$$1 \leq i \lt N$$$, if the employee with capability values $$$i+1$$$ is selected for the trip but the employee with capability values $$$i$$$ is not, a further loss of $$$d_i$$$ million dollars will occur.
But wait! Before ICPC Company decides on the personnel to dispatch, they need to quickly inform the client whether they will accept the project. For this reason, ICPC Company has commissioned you, with your algorithmic expertise, to help them evaluate the maximum potential profit they could achieve.
However, ICPC Company knows an obvious upper bound: the total profit cannot exceed $$$T = \sum_{i=1}^{N}\max(p_i, 0)$$$ million dollars. After careful evaluation, ICPC Company has decided that if the maximum profit from this business trip is less than $$$T - 20$$$ million dollars, they will immediately reject the project; otherwise, they will begin planning for the trip.
Can you help ICPC Company determine whether they should take on the project? If they decide to take on the project, please also output the exact maximum profit that ICPC Company can achieve.
The input first contains a positive integer $$$N$$$, representing the number of employees in ICPC Company.
The next line contains $$$N-1$$$ integers $$$s_2, s_3, \ldots, s_N$$$, where $$$s_i$$$ represents the direct supervisor of the $$$i$$$-th employee.
The third line contains $$$N$$$ integers $$$p_1, p_2, \ldots, p_N$$$, representing the profit the $$$i$$$-th employee can bring.
The fourth line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$, representing the capability value of the $$$i$$$-th employee.
The fifth line contains $$$N$$$ integers $$$c_1, c_2, \ldots, c_N$$$, representing the loss parameter of the $$$i$$$-th employee.
The sixth line contains $$$N-1$$$ integers $$$d_1, d_2, \ldots, d_{N-1}$$$, representing the loss parameter between the employees with capability values $$$i$$$ and $$$i+1$$$.
If the maximum profit is less than $$$T - 20$$$ million dollars, output Fail! on a single line. Otherwise, output a single integer representing the maximum profit that ICPC Company can achieve under the optimal strategy for selecting employees to send on the business trip.
41 2 210 -6 6 24 3 2 11 1 1 51 1 1
13
61 2 2 4 4-3 -10 9 -1 4 71 4 3 6 5 20 1 8 1 3 11 5 0 0 2
9
21-42 212 10 420
Fail!
