#1520 · Tiệm Tóc Tiên Tiến

Tiên và Tiến đang là thợ cắt tóc của tiệm Tóc Tiên Tiến. Trong đó Tiên có thể hoàn thành A công việc mỗi phút, còn Tiến có thể hoàn thành B công việc mỗi phút.

Giả sử có N khách hàng cần hẹn lịch cắt tóc, mỗi khách hàng có kiểu tóc khác nhau nên cũng cần có khối lượng công việc cần hoàn thành khác nhau. Khách hàng thứ i có khối lượng công việc cần hoàn thành là W_i.

Biết rằng mỗi khách hàng chỉ được phục vụ bởi một thợ cắt tóc. Tiên và Tiến muốn kết thúc công việc cùng nhau nên hai người cần phải tính toán phân phối công việc. Họ sẽ về nhà sau khi khách hàng cuối cùng được hoàn thành.

Bạn hãy giúp họ xác định thời gian ít nhất để hoàn thành công việc trong ngày?

Dòng đầu tiên chứa ba số nguyên N, A và B cách nhau bởi dấu cách. Dòng thứ hai chứa N số nguyên là khối lượng công việc của từng khách hàng W_i,W_i, ...,W_N.

1 dòng duy nhất là thời gian ít nhất cần để hoàn thành công việc trong ngày hôm đó