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ó \(10^9\) màu sắc khác nhau được đánh số từ 1 tới \(10^9\)
• Ở 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ể. Sau khi kết thúc ván đấu, 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:

Input

• Dòng đầu tiên chứa số \(n, a, b\) \((1 \leq n \leq 10^9; 1 \leq a, b \leq 10^9)\), 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ố \(A_1, A_2, \ldots, A_n\) \((1 \leq A_i \leq 10^9, \forall 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 \leq 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 quá hai quân cờ
• Subtask 4 (28% số điểm): Không có ràng buộc gì thêm

Example

8 1 1
4 2 1 3 5 1 2 1

5