Alice được giao thực hiện \(n\) công việc, cô đã đánh số các công việc từ \(1\) đến \(n\) và tính toán công việc thứ \(i\) (\(1 \le i \le n\)) có đặc điểm như sau:

• Thời gian thực hiện là \(t_i\).
• Mức độ quan trọng là \(w_i\) nên nếu công việc \(i\) kết thúc tại thời điểm \(d\) thì sẽ mất chi phí \(d \times w_i\).
• Công việc \(p_i\) phải được thực hiện trước công việc \(i\) (\(p_i < i\)). Chỉ có duy nhất \(p_1 = 0\) nghĩa là chỉ có công việc \(1\) có thể thực hiện ngay thời điểm \(0\) đầu tiên.

Alice cần lập lịch để tổng chi phí thực hiện cả \(n\) công việc là nhỏ nhất. Tuy nhiên, Alice có thể thay đổi trọng số của một công việc nào đó thành \(1\).

Yêu cầu: Hãy giúp Alice tìm cách thay đổi trọng số của một công việc để chi phí thực hiện của cả \(n\) công việc là nhỏ nhất.

Input

• Dòng đầu là số nguyên dương \(n\) là số công việc.
• Dòng thứ hai gồm \(n\) số mô tả mảng \(p\).
• Dòng thứ ba gồm \(n\) số nguyên không âm mô tả mảng \(w\) (\(w_i \le 10^3\)).
• Dòng cuối cùng gồm \(n\) số nguyên không âm mô tả mảng \(t\) (\(t_i \le 10^3\)).

Output

• Một dòng chứa một số là tổng chi phí nhỏ nhất tìm được.

Example

3
0 1 1
2 3 3
1 2 3

17

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 8\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 18\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 180\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 1800\).