Nhà gỗ

Công ty WooHome vừa nhập khẩu \(N\) cột gỗ có chiều cao lần lượt là \(A_1, A_2, \dots, A_N\).
Công ty có \(M\) mẫu thiết kế nhà; mẫu thứ \(i\) \((1 \le i \le M)\) cần đúng \(S_i\) cột gỗ để làm cột trụ cho một ngôi nhà.
Với mỗi ngôi nhà được đặt hàng theo một trong \(M\) mẫu, công ty có lợi nhuận cố định là \(P\).

Tuy nhiên, các cột gỗ dùng trong một ngôi nhà có thể không đều nhau. Chi phí để khắc phục sự không đồng đều là

trong đó \(C\) là hệ số giá thành thi công, \(\max\) và \(\min\) lần lượt là chiều cao lớn nhất và nhỏ nhất trong các cột gỗ dùng cho ngôi nhà đó.

Vì vậy, lợi nhuận dự kiến khi thi công một ngôi nhà là

Lưu ý rằng lợi nhuận có thể âm.

WooHome muốn đáp ứng trước các đơn đặt hàng sao cho mỗi mẫu nhà có ít nhất một ngôi nhà được thi công,
và mỗi cột gỗ được dùng tối đa một lần (có thể có cột không dùng).

Hãy tìm tổng lợi nhuận dự kiến lớn nhất.

\InputFile
Dòng đầu chứa bốn số nguyên dương \(N, M, P, C\).

Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\).

Dòng thứ ba chứa \(M\) số nguyên dương \(S_1, S_2, \ldots, S_M\).

\OutputFile
In ra một số nguyên là tổng lợi nhuận dự kiến lớn nhất.

Ràng buộc

• \(N \le 10^5\), \(M \le 6\), \(P \le 10^9\), \(C \le 10^6\).
• \(A_i \le 10^6\).
• \(2 \le S_i \le N\).
• \(\sum_{i=1}^{M} S_i \le N\).

\Scoring

• Subtask 1 (25%): \(N \le 10\), \(M = 1\).
• Subtask 2 (25%): \(N \le 1000\), \(M = 1\), \(S_1 = 2\).
• Subtask 3 (25%): \(M = 2\).
• Subtask 4 (25%): không có ràng buộc thêm.

Example

10 2 11 1
14 5 6 4 4 4 7 8 9 1
4 2

30

4 1 7 2
8 5 4 7
3

-11