Tý có một xí nghiệp sản xuất \(N\) lô hàng. Lô thứ \(i\) có chi phí nguyên liệu \(a_i\) và thời gian sản xuất \(b_i\). Nếu lô hàng \(i\) được sản xuất ngay sau lô \(j\), chi phí chuyển đổi là \(a_j \times b_i\). Mỗi lô còn có chi phí riêng \(c_i\).

Tổng chi phí để sản xuất đến lô thứ \(i\): \[F_i = \min_{j < i} \{ F_j + a_j \times b_i + c_i \}\]

với \(F_1 = c_1\). Hãy tính \(F_N\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Dữ liệu vào

• Dòng đầu gồm \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai gồm \(N\) số \(a_i\) (\(|a_i| \le 10^6\), \(a_i\) giảm dần).
• Dòng thứ ba gồm \(N\) số \(b_i\) (\(|b_i| \le 10^6\), \(b_i\) tăng dần).
• Dòng thứ tư gồm \(N\) số \(c_i\) (\(|c_i| \le 10^6\)).

Kết quả ra

• In ra \(F_N\).

Ví dụ

Input

4
5 3 2 1
1 4 6 9
1 2 3 4

Output

27

Subtask