giúp tui với mn ơi

Hùng là một con người tự do, thích khám phá những điều mới lạ; vì vậy, cậu rất thích những bộ môn có chữ "freestyle", cụ thể là freestyle rap và mới đây nhất là Freestyle Chess.

Mới đây, giải đầu tiên thuộc hệ thống giải đấu Grand Slam của Freestyle Chess (một tổ chức chuyên tổ chức các giải đấu cờ ngẫu nhiên Fischer, là một thể thức cờ vua mà hàng 1 bên trắng và hàng 8 bên đen được xáo trộn ngẫu nhiên sao cho hai Tượng của mỗi bên phải nằm ở hai ô màu khác nhau và Vua phải nằm giữa hai Xe).

Sau khi Hùng thấy thần tượng Carlsen của mình dừng chân tại bán kết, Hùng quyết định vung tiền để mở giải Freestyle Array Picker, với hy vọng mời được anh ta về làm quán quân đầu tiên của môn cờ mới này.

Trò chơi hai người này gồm một bàn cờ có n quân cờ. Hai bên cũng được gọi là bên Trắng và bên Đen. Tuy nhiên, đúng với chất "freestyle", luật chơi chứa rất nhiều thứ ngẫu nhiên và tự do:

• Các quân cờ không chỉ có màu Trắng hoặc Đen, mà có thể có 109 màu sắc khác nhau được đánh số từ 1 tới 109.
• Ở mỗi trận đấu, màu sắc của n quân cờ được tô ngẫu nhiên.
• Bên Trắng đi trước, hai người chơi sẽ lần lượt bốc các quân cờ còn nằm trên bàn cờ và đưa về kho của mình.
• Trò chơi kết thúc khi không còn quân cờ trên bàn cờ nữa.

Tuy nhiên, tự do bao giờ cũng kèm theo nguyên tắc và mục tiêu. Bên Trắng cần làm cho số điểm của mình cao nhất có thể, trong khi bên Đen cần tìm cách để hạ số điểm của Trắng xuống thấp nhất có thể. Số điểm của bên Trắng được tính như sau:

• a điểm cho mỗi màu mà bên Trắng bốc trước bên Đen;
• b điểm cho mỗi màu sắc mà bên Trắng có nhưng bên Đen không có.

Mỗi ván đấu gồm hai hiệp với bàn cờ giống nhau, người chơi hiệp này cầm quân Trắng thì hiệp kia cầm quân Đen và ngược lại; người chơi nào đạt được nhiều điểm hơn khi cầm quân Trắng sẽ thắng. Ở trong các giải đấu chính thức, thường sẽ có hai thể thức: một là ván này cầm quân Trắng ở hiệp đầu thì ván sau hiệp đầu cầm quân Đen, hai là chơi hai hiệp cùng lúc với nhau.

Sau khi (giả vờ) bốc thăm xếp cặp thi đấu, (để tăng sức hút (nhất là với khán giả Việt Nam), Hùng đã dàn xếp để) trận khai mạc giải Freestyle Array Picker sẽ là cuộc so tài giữa Magnus Carlsen và Lê Quang Liêm. Đồng thời, để thỏa mãn người xem, Hùng sẽ truyền hình trực tiếp toàn bộ các trận đấu của giải lên các nền tảng streaming, với đồ họa hình ảnh như một giải đấu cờ thực thụ.

Nếu bạn xem các giải đấu cờ khác, bạn sẽ thấy bên cạnh bàn cờ là một AI dự đoán kết quả, với xác suất thắng của mỗi bên hoặc chiếu hết trong bao nhiêu nước. Tuy nhiên, luật chơi của Array Picker quá phức tạp, nên khó để tính xác suất thắng, tuy nhiên ta có thể tính được số điểm tối đa của bên Trắng sau mỗi lượt đi.

Bạn được thuê về để làm AI cho giải đấu, và sau đây là khởi đầu cho công việc:

Yêu cầu: Cho bàn cờ ban đầu. Giả sử hai bên chơi tối ưu nhất, tức bên Trắng luôn tìm cách để điểm số cao nhất, trong khi bên Đen tìm cách để điểm số của Trắng thấp nhất; hãy tính số điểm tối đa đạt được của bên Trắng khi ván đấu kết thúc.

Input

• Dòng đầu tiên chứa số n,a,b (1≤n≤106;1≤a,b≤109), lần lượt là số lượng quân cờ trên bàn cờ, và hai mức điểm tương ứng khi bốc quân đầu tiên và toàn bộ quân của mỗi màu.
• Dòng thứ hai chứa n số A1,A2,…,An (1≤Ai≤109,∀i) lần lượt là màu sắc của n quân cờ trên bàn cờ.

Output

• Gồm một số duy nhất là số điểm tối đa mà bên Trắng đạt được khi hai bên đều chơi nước đi tối ưu nhất ở mỗi lượt đi.

Scoring

• Subtask 1 (27% số điểm): n≤20
• Subtask 2 (20% số điểm): Màu của các quân cờ khác nhau đôi một.
• Subtask 3 (25% số điểm): Mỗi màu được tô lên không qua hai quân cờ
• Subtask 4 (28% số điểm): Không có ràng buộc gì thêm

Example

Sample Input 1

Copy8 1 1 4 2 1 3 5 1 2 1

Sample Output 1

Copy5

Note

Biên bản ván chơi như sau: W1++ B4 W5++ B2 W3+ B6 W8 B7, với mỗi nước đi được ký hiệu là ci với c là lượt đi của Trắng(W) hay Đen(B), i thể hiện việc chọn quân Ai, và mỗi dấu + biểu thị một điểm cho bên Trắng. 

làm c++