Công ty WooHome thiết kế lắp ráp nhà gỗ vừa nhập khẩu $N$ cột gỗ loại đặc biệt có chiều cao lần lượt là $A_1,A_2,\dots ,A_N$. Công ty cho ra mắt $M$ mẫu thiết kế nhà, mẫu nhà thứ $i$ $(1\le i\le M)$ cần $S_i$ cột trong số $N$ cột gỗ trên làm cột trụ cho một ngôi nhà. Phòng kinh doanh của công ty đã tính toán với mỗi ngôi nhà gỗ được đặt hàng theo một trong $M$ mẫu trên, công ty sẽ có thêm một khoản lợi nhuận cố định có giá trị là $P$.

Tuy nhiên, các cột gỗ được chọn cho ngôi nhà thi công có thể có chiều cao không đều nhau, nên khi thi công sẽ phải khắc phục để đảm bảo sự chắc chắn của ngôi nhà. Phòng kinh doanh dự kiến chi phí để khắc phục sự không đồng đều chiều cao các cột bằng một giá trị $(max-min{)}^2\times C$, với $C$ là hệ số giá thành thi công, $max$ và $min$ lần lượt là chiều cao cột gỗ lớn nhất và nhỏ nhất trong số những cột gỗ sử dụng cho ngôi nhà thi công. Như vậy, lợi nhuận dự kiến khi thi công một ngôi nhà theo mẫu là $P-(max-min{)}^2\times C$. Ví dụ, với giá trị lợi nhuận cố định $P=10$, một ngôi nhà thi công sử dụng $5$ cột gỗ có chiều cao lần lượt là $4,5,3,4,5$, hệ số $C=1$, thì công ty sẽ có lợi nhuận dự kiến là $10-(5-3{)}^2\times 1=6$. Lưu ý rằng mức lợi nhuận dự kiến có thể âm.

Là một công ty có thương hiệu, WooHome luôn có rất nhiều đơn đặt hàng cho mỗi mẫu nhà mới. Vì đây là các mẫu mới ra mắt, công ty 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.

Yêu cầu: Hãy giúp công ty tìm ra số lượng ngôi nhà thi công mỗi mẫu sao cho đạt được tối đa lợi nhuận dự kiến, thỏa mãn mỗi mẫu nhà có ít nhất một ngôi nhà được thi công và mỗi cột được dùng tối đa một lần.

Dữ liệu

Vào từ file văn bản WHOME.INP:

• Dòng đầu chứa bốn số nguyên dương $N,M,P$ và $C$ $(N\le {10}^5;M\le 6;P\le {10}^9;C\le {10}^6)$.

• Dòng thứ hai chứa $N$ số nguyên dương $A_1,A_2,\dots ,A_N$ $(A_i\le {10}^6,\mathrm{\forall }i=1,2,\dots ,N)$.

• Dòng thứ ba chứa $M$ số nguyên dương $S_1,S_2,\dots ,S_M$ $(2\le S_i\le N,\mathrm{\forall }i=1,2,\dots ,M)$

Dữ liệu bảo đảm $\sum _{i=1}^M{S}_i\le N$ và $S_i\ne S_j$ ($\mathrm{\forall }i,j:1\le i<j\le M$).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản WHOME.OUT một số nguyên là tổng lợi nhuận dự kiến lớn nhất tìm được.

Ràng buộc

• Có $25\mathrm{\%}$ số test ứng với $25\mathrm{\%}$ số điểm thỏa mãn: $N\le 10;M=1$.

• $25\mathrm{\%}$ số test khác ứng với $25\mathrm{\%}$ số điểm thỏa mãn: $N\le 1000;M=1;S_1=2$.

• $25\mathrm{\%}$ số test khác ứng với $25\mathrm{\%}$ số điểm thỏa mãn: $M=2$.

• $25\mathrm{\%}$ số test còn lại ứng với $25\mathrm{\%}$ số điểm không có ràng buộc gì thêm.

Ví dụ 1

Input

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

Output

30

Giải thích

Lựa chọn tốt nhất là:

• Mẫu 1: Thi công một ngôi nhà với $4$ cột gỗ $5,4,4,4$ cho lợi nhuận dự kiến là $11-(5-4{)}^2\times 1=10$.

• Mẫu 2: Thi công hai ngôi nhà, ngôi nhà thứ nhất gồm 2 cột gỗ $6,7$ cho lợi nhuận dự kiến là $11-(7-6{)}^2\times 1=10$, và ngôi nhà thứ hai gồm 2 cột gỗ $8,9$ cho lợi nhuận dự kiến là $11-(9-8{)}^2\times 1=10$.

Tổng lợi nhuận dự kiến là $30$.

Ví dụ 2

Input

4 1 7 2
8 5 4 7
3

Output

-11

Giải thích

Một lựa chọn tốt nhất là thi công ngôi nhà với 3 cột $8,5,7$ cho lợi nhuận dự kiến là $7-(8-5{)}^2\times 2=-11$.