Đất

Cho một lưới đất kích thước \(2 \times n\), được chia thành \(2n\) ô vuông nhỏ \(1 \times 1\). Ô ở hàng \(i\) (\(1 \le i \le 2\)), cột \(j\) (\(1 \le j \le n\)) mang lại giá trị là \(A_{i, j}\) nếu bạn sở hữu nó. Cụ thể, \(A_{1, j}\) là giá trị ô ở hàng 1 cột \(j\), và \(A_{2, j}\) là giá trị ô ở hàng 2 cột \(j\).

Bạn có thể mua ba loại đất với kích thước và giá thành như sau:

• Loại 1: mua mảnh đất \(1 \times 1\) với giá \(x\).

• Loại 2: mua mảnh đất \(1 \times 2\) (hoặc \(2 \times 1\)) với giá \(y\).

• Loại 3: mua mảnh đất \(2 \times 2\) với giá \(z\).

Các mảnh đất đã mua phải khớp chính xác với các ô lưới và không được đè lên nhau. Mỗi ô chỉ được phủ bởi tối đa một mảnh đất (có thể để trống không mua một số ô).

Lợi nhuận bạn thu được bằng tổng giá trị của tất cả các ô đất bạn sở hữu trừ đi tổng số tiền bạn đã bỏ ra để mua các mảnh đất đó. Hãy tìm lợi nhuận lớn nhất có thể đạt được.

Input

• Dòng đầu tiên gồm bốn số nguyên \(n, x, y, z\) (\(1 \le n \le 500\), \(1 \le x, y, z \le 1000\)).

• \(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(A_i, B_i\) (\(0 \le A_i, B_i \le 10\)).

Output

In ra một số nguyên là chi phí nhỏ nhất.

Example

Input:

4 100 200 1
1 4
2 3
3 2
4 0

Output:

210

Note

Trong ví dụ trên, khu đất 1 thiếu 3 đơn vị, khu đất 2 thiếu 1 đơn vị, khu đất 3 dư 1 đơn vị, khu đất 4 dư 4 đơn vị. Một phương án tối ưu: chuyển 1 đơn vị đất từ khu đất 3 sang khu đất 2 (giá \(|3-2|\times 1=1\)), chuyển 3 đơn vị đất từ khu đất 4 sang khu đất 1 (giá \(|4-1|\times 1\times 3=9\)), và bỏ đi 1 đơn vị đất còn dư ở khu đất 4 (giá \(200\)). Tổng chi phí là \(1+9+200=210\).