Công ty của Alice vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của robot, Alice tạo ra một bức tường từ \(n\) cột các khối lập phương, các cột đặt cạnh nhau, bề dày bức tường là \(1\) và với độ cao tương ứng là \(a_1, a_2, \ldots, a_n\), trong đó \(a_i\) là độ cao cột thứ \(i\) (do \(a_i\) khối lập phương tạo lên). Robot được giao nhiệm vụ thay đổi bức tường với độ cao tương ứng là \(b_1, b_2, \ldots, b_n\). Robot chỉ có thể thực hiện một trong ba loại thao tác sau:

• Thao tác 1: Lấy khối trên cùng của một cột để bỏ đi, thời gian thực hiện thao tác này là \(x\);
• Thao tác 2: Lấy một khối mới, đặt khối đó lên trên cùng của một cột, thời gian thực hiện thao tác này là \(y\);
• Thao tác 3: Chuyển một khối từ cột \(i\) sang cột \(j\), thời gian thực hiện thao tác này là \(z \cdot |i-j|\).

Yêu cầu: Cho \(a_1, a_2, \ldots, a_n\); \(b_1, b_2, \ldots, b_n\) và \(x, y, z\). Hãy xác định thời gian ngắn nhất để robot hoàn thành nhiệm vụ.

Input

• Dòng đầu chứa bốn số nguyên dương \(n, x, y, z\) (\(x, y, z \le 1000\));
• Dòng thứ hai gồm \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10\));
• Dòng thứ ba gồm \(n\) số nguyên không âm \(b_1, b_2, \ldots, b_n\) (\(b_i \le 10\)).

Output

• Ghi ra một dòng chứa một số nguyên là thời gian ít nhất để robot hoàn thành nhiệm vụ.

Example

4 10 10 1
1 2 2 4
2 2 2 2

13

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\) và \(a_i, b_i \le 1\);
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10^2\) và \(a_i, b_i \le 1\);
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 10^3\);
• Subtask \(4\) (\(25\%\) số điểm): \(n \le 10^5\).