Cho \(N\) nhà máy có lượng phát thải \(A_1, A_2, \dots, A_N\). Cần đưa phát thải mỗi nhà máy về đúng giá trị \(K\). Việc chuyển \(1\) đơn vị phát thải giữa nhà máy \(i\) và nhà máy \(i+1\) tốn chi phí \(C_i\).

Hãy tính tổng chi phí tối thiểu, hoặc in ra \(-1\) nếu tổng phát thải ban đầu khác \(N \cdot K\).

Input

• Dòng \(1\): Hai số nguyên \(N, K\) (\(N \le 10^5, K \le 10^9\)).
• Dòng \(2\): \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(A_i \le 10^9\)).
• Dòng \(3\): \(N-1\) số nguyên \(C_1, C_2, \dots, C_{N-1}\) (\(C_i \le 10^6\)).

Output

• In ra một số nguyên duy nhất là chi phí tối thiểu tìm được, hoặc \(-1\) nếu không thể thực hiện yêu cầu. (Đối với các trường hợp khác \(-1\) cần in ra đáp án chia lấy dư cho \(10^9+7\))

Example

4 3
5 1 2 4
10 2 5

25

3 5
2 4 6
1 1

-1