Đêm Halloween, có \(n\) ngôi nhà trên một khu phố tham gia vào một "cuộc chiến" phát kẹo. Các ngôi nhà nằm liên tiếp nhau trên một con đường và được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái sang phải. Mục tiêu của mỗi nhà là phải "thoát" khỏi đêm Halloween với một số lượng kẹo nhất định.

Hiện tại, nhà thứ \(i\) có \(a_i\) giỏ kẹo. Theo quy định của khu phố, để được coi là "thành công", nhà thứ \(i\) phải kết thúc đêm với đúng \(b_i\) giỏ kẹo.

Trong suốt đêm, ba sự kiện có thể xảy ra:

• Treat:
  Có một dịch vụ giao kẹo khẩn cấp. Bạn có thể gọi họ mang \(1\) giỏ kẹo mới đến nhà thứ \(i\). Chi phí cho mỗi giỏ kẹo đặt thêm này là \(X\).
• Trick:
  Cứ thỉnh thoảng, một nhóm nhóc tinh nghịch (tricksters) lại chạy qua. Nếu chúng nhắm vào nhà thứ \(i\), chúng sẽ "xử lý" (làm hỏng, làm đổ, ném lung tung) 1 giỏ kẹo của bạn. Bạn không thể dùng giỏ kẹo đó nữa, và tốn chi phí \(Y\) để dọn dẹp mớ hỗn độn đó.
• Share:
  Các nhà hàng xóm có thể giúp đỡ lẫn nhau. Nhà thứ \(i\) có thể bí mật mang 1 giỏ kẹo của mình chạy sang đưa cho nhà \(j\). Vì phải chạy qua lại trong đêm tối, chi phí công sức để di chuyển 1 giỏ kẹo từ nhà thứ \(i\) sang nhà thứ \(j\) là \(Z \cdot |i - j|\).

Hãy tính tổng chi phí nhỏ nhất để tất cả các nhà đều thành công.

Dữ liệu

Vào từ file văn bản trortr.inp:

• Dòng đầu tiên chứa một số nguyên \(\theta\) là số bộ dữ liệu.
• Tiếp theo là các bộ dữ liệu, mỗi bộ được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai gồm bốn số nguyên \(n\), \(X\), \(Y\), \(Z\) \((1 \leq n \leq 2 \cdot 10^5, 1 \leq X, Y, Z \leq 10^6)\).
  • Dòng thứ ba gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^7)\).
  • Dòng thứ tư gồm \(n\) số nguyên \(b_1, b_2, \ldots, b_n\) \((1 \leq b_i \leq 10^7)\).

Gọi:

• \(\Sigma_n\) là tổng giá trị của \(n\) trong các bộ dữ liệu;
• \(\Sigma_a\) là tổng giá trị của \(a_1 + a_2 + \ldots + a_n\) trong các bộ dữ liệu;
• \(\Sigma_b\) là tổng giá trị của \(b_1 + b_2 + \ldots + b_n\) trong các bộ dữ liệu.

Dữ liệu đảm bảo \(\Sigma_n \leq 10^6\).

Kết quả

Ghi ra file văn bản trortr.out:

• Với mỗi bộ dữ liệu, in ra tổng chi phí nhỏ nhất trên một dòng.

Ràng buộc

• Subtask \(1\) (\(11\) điểm): \(X + Y \leq Z\).
• Subtask \(2\) (\(17\) điểm): \(X = Y = Z\) và \(a_i, b_i \leq 20\).
• Subtask \(3\) (\(19\) điểm): \(n \leq 80\) và \(\Sigma_n \leq 400\).
• Subtask \(4\) (\(19\) điểm):
  • \(a_1 + a_2 + \ldots + a_n \leq 3000\) và \(\Sigma_a \leq 15000\).
  • \(b_1 + b_2 + \ldots + b_n \leq 3000\) và \(\Sigma_b \leq 15000\).
• Subtask \(5\) (\(17\) điểm): \(n \leq 3000\) và \(S_n \leq 15000\).
• Subtask \(6\) (\(17\) điểm): Không có ràng buộc gì thêm.

Ví dụ

2

2 6 7 15
3 13
11 24

2 2 2 7
1 9
9 7

114
20