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, \ldots, A_N~ ~(A_i \le 10^6, \forall i = 1, 2, \dots, N)~.

• Dòng thứ ba chứa ~M~ số nguyên dương ~S_1, S_2, \ldots, S_M~ ~(2 \le S_i \le N, \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~ (~\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\%~ số test ứng với ~25\%~ số điểm thỏa mãn: ~N \le 10; M = 1~.

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

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

• ~25\%~ số test còn lại ứng với ~25\%~ 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~.

Công ty S-HOME đang thiết kế một mẫu nhà thông minh thế hệ mới được trang bị ~K~ thiết bị thông minh. Bản thiết kế được vẽ trên mặt phẳng toạ độ ~Oxy~ với gốc toạ độ ~(0,0)~ là nơi đặt trung tâm điều khiển tất cả các thiết bị. Trên bản vẽ, kỹ sư thiết kế vạch ra ~N~ vùng hình chữ nhật quan trọng có các cạnh song song với hai trục ~Ox~ và ~Oy~, nơi mà các thiết bị thông minh có thể được đặt vào. Các vùng hình chữ nhật được đánh số từ ~1~ đến ~N~, vùng thứ ~i~ ~(1 \le i \le N)~ được cho bởi bộ ~(L_i, B_i, R_i, T_i)~ với toạ độ góc trái dưới là ~(L_i, B_i)~ và góc phải trên là ~(R_i, T_i)~. Lưu ý rằng các vùng hình chữ nhật này có thể giao nhau.

Mỗi thiết bị thông minh sẽ được đặt tại một điểm có toạ độ nguyên dương ~(x, y)~ và phải nằm trong hoặc nằm trên cạnh của ít nhất một vùng hình chữ nhật quan trọng. Thiết bị này được điều khiển trực tiếp bởi trung tâm điều khiển tại ~(0,0)~ và có chi phí lắp đặt kết nối bằng ~(x+y)~. Điểm ~(x,y)~ gọi là nằm trong hoặc trên cạnh vùng hình chữ nhật quan trọng thứ ~i~ khi và chỉ khi ~L_i \le x \le R_i~ và ~B_i \le y \le T_i~.

Yêu cầu: Hãy giúp công ty S-HOME xác định ~K~ vị trí đặt thiết bị thông minh để chi phí lớn nhất trong số các chi phí lắp đặt kết nối tới trung tâm điều khiển của ~K~ thiết bị nêu trên là nhỏ nhất. Lưu ý rằng các thiết bị thông minh không được đặt trùng vị trí của nhau.

Dữ liệu

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

• Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ ~(N \le 50000; K \le 10^{18})~.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa bốn số nguyên dương ~L_i~, ~B_i~, ~R_i~, ~T_i~ ~(L_i < R_i \le 5 \times 10^7; B_i < T_i \le 5 \times 10^7)~.

Dữ liệu đảm bảo giá trị ~K~ không lớn hơn tổng số điểm có toạ độ nguyên dương nằm trong hoặc trên cạnh của ít nhất một vùng hình chữ nhật quan trọng.

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 SDEV.OUT một số nguyên duy nhất là giá trị nhỏ nhất tìm được của chi phí lớn nhất trong số các chi phí lắp đặt kết nối tới trung tâm điều khiển của ~K~ thiết bị.

Ràng buộc

• Có ~16\%~ số test ứng với ~16\%~ số điểm thỏa mãn: ~N \le 100; R_i, T_i \le 1000, \forall i = 1,2,\dots,N~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~N \le 15~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~N \le 1000~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~R_i, T_i \le 10^5, \forall i = 1,2,\dots,N~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~K\le 10^5~.

• ~12\%~ số test còn lại ứng với ~12\%~ số điểm không có ràng buộc gì thêm

Ví dụ

Input

2 10
1 2 3 4
2 1 4 3

Output

6

Giải thích

Một trong các phương án tối ưu là các thiết bị thông minh được đặt lần lượt tại các vị trí ~(1, 2)~, ~(1, 3)~, ~(1, 4)~, ~(2, 1)~, ~(2, 2)~, ~(2, 3)~, ~(3, 1)~, ~(3, 2)~, ~(3, 3)~, ~(4, 1)~ với chi phí lớn nhất cần tìm là chi phí lắp đặt của thiết bị tại ô ~(3, 3)~.

Trong một vương quốc có ~N~ vùng, được đánh số từ ~1~ đến ~N~, vùng được đánh số ~1~ là kinh đô của vương quốc. Có đúng ~N-1~ con đường nối trực tiếp giữa các vùng với nhau đảm bảo mỗi vùng đều có thể tới kinh đô thông qua các con đường này. Vương quốc thực hiện phương cách quản lý phân cấp từ kinh đô tới các vùng bên dưới. Cụ thể, vùng ~X~ được gọi là quản lý vùng ~Y~ nếu mọi cách di chuyển thông qua các con đường từ vùng ~Y~ tới kinh đô đều luôn đi qua vùng ~X~.

Các vùng đều có các thửa ruộng có thể canh tác lương thực trên đó, vùng thứ ~i~ ~(1\le i \le N)~ có ~Q_i~ thửa ruộng, mỗi thửa ruộng nếu canh tác dự kiến sẽ cho sản lượng đúng ~W_i~ tấn. Nhà vua mong muốn tổng sản lượng lương thực trên toàn vương quốc phải đạt tối thiểu ~S~ tấn, biết rằng:

• Do đặc thù mỗi vùng, vùng thứ ~i~ nếu sử dụng ~K_i~ thửa ruộng để canh tác lương thực sẽ tốn tổng chi phí canh tác và bảo vệ mùa màng là ~K_i^2\times C_i~.

• Nếu vùng ~X~ không sử dụng thửa ruộng nào để canh tác lương thực thì tất cả các vùng mà ~X~ quản lý cũng đều không canh tác lương thực.

Yêu cầu: Hãy giúp nhà vua xác định dãy ~(K_1,K_2,...,K_N)~ là số lượng thửa ruộng tương ứng được phân công canh tác cho từng vùng, sao cho tổng chi phí canh tác và bảo vệ mùa màng là nhỏ nhất mà vẫn đạt được sản lượng mong muốn của nhà vua, hoặc thông báo là không có cách phân công nào thỏa mãn.

Dữ liệu

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

• Dòng đầu ghi hai số nguyên dương ~N~ và ~S~ ~(N,S\le 5000)~.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo ghi ba số nguyên dương ~Q_i,W_i~ và ~C_i~ ~(Q_i,W_i\le 5000;C_i\le10^6)~.

• Mỗi dòng trong ~N-1~ dòng tiếp theo ghi hai số nguyên dương ~u~ và ~v~ ~(1\le u,v \le N)~ thể hiện có con đường nối trực tiếp giữa hai vùng ~u~ và ~v~.

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 FOOD.OUT một số nguyên duy nhất là tổng chi phí canh tác và bảo vệ mùa màng nhỏ nhất tìm được. Ghi ra ~-1~ nếu không có phương án phân công nào thỏa mãn.

Ràng buộc

• Có ~16\%~ số test ứng với ~16\%~ số điểm thỏa mãn: ~Q_i=1,\forall i=1,2,...,N~ và có các con đường trực tiếp từ kinh đô đến tất cả các vùng khác.

• ~14\%~ số test khác ứng với ~14\%~ số điểm thỏa mãn: ~N,S\le 500~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~Q_i=W_i=1,\forall i=1,2,...,N~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~Q_i=1,\forall i=1,2,...,N~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: Có các con đường trực tiếp từ kinh đô đến tất cả các vùng khác.

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

Ví dụ

Input

6 9
2 1 5
4 3 1
1 3 2
1 2 4
1 1 10
1 7 1
1 2
2 3
2 4
1 5
5 6

Output

11

Giải thích

Dãy ~(K_1,K_2,K_3,K_4,K_5,K_6)=(1,2,1,0,0,0)~ cho tổng sản lượng lương thực là:

~1 \times 1 + 2 \times 3 + 1 \times 3 + 0 \times 2 + 0 \times 1 + 0 \times 7 = 10 \ge 9~,

và là dãy cho chi phí nhỏ nhất cần tìm bằng: ~1^2 \times 5 + 2^2 \times 1 + 1^2 \times 2 + 0^2 \times 4 + 0^2 \times 10 + 0^2 \times 1 = 11~.