TAHO2 - Tặng hoa 8/3
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 5.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Nhân ngày Quốc tế Phụ nữa 8/3 sắp tới, bạn An quyết định mua một bó hoa thật đẹp tặng cho Vân - cô gái mà cậu luôn thầm thương trộm nhớ và cũng là cơ hội để bày tỏ tình cảm của mình. An đi đến một cửa hàng đồng giá, ở đây tất cả các loại hoa đề được bán với cùng một giá, tuy nhiên với mỗi loại hoa, bạn chỉ có thể mua tối đa 1 bông hoa để tránh việc các loại hoa quý và đẹp bị mua hết. Vân có những quan niệm rất đặc biệt, theo cô thì mỗi loại hoa đều tượng trưng cho một con số may mắn nào đó và bạn An cũng chúng ta đã bằng một cách nào đó có được danh sách các loại hoa và con số tương ứng này. Vân cũng có một con số yêu thích S của mình, cá tính của cô ấy rất đặc biệt, nếu bất kì ai tặng quà cho cô ấy mà không có liên quan đến con số này thì cô ấy sẽ giận ngay. Tất nhiên là An không muốn điều này xảy ra vì như thế thì xem như cơ hội bày tỏ tình cảm cũng không còn, như thế thì thà không tặng còn hơn.

An quyết định sẽ tặng cho Vân một bó hoa có tổng các con số may mắn của các đóa hoa đúng bằng S. Nhưng vì đang là sinh viên, không có nhiều tiền nên An muốn tìm ra cách mua bó hoa sao cho tổng chi phí phải trả là thấp nhất. Bạn hãy giúp An thực hiện việc này nhé.

Dữ liệu nhập:

 - Dòng đầu tiên chứa 3 số nguyên N, S, P. N là số lượng hoa có trong cửa hàng (1 ≤ N ≤ 40), S là con số yêu thích của Vân (0 ≤ S ≤ 109) và P là giá của mỗi đóa hoa (1 ≤ P ≤ 106).

 - Dòng tiếp theo chứa N số nguyên dương Ai không vượt quát 109 là con số may mắn tương ứng với loại hoa thứ i.

Dữ liệu xuất: Nếu có cách mua hoa thỏa yêu cầu thì xuất ra giá của bó hoa mà An phải chi trả. Nếu không tìm ghép được bó hoa ưng ý thì xuất ra -1.

Ví dụ

  • input
    10 390 2
    200 10 20 20 50 50 50 50 100 100
    output
    10
Back to Top