TAHO2 - Tặng hoa 8/3

Mô tả

Nhân ngày Quốc tế Phụ nữa 8/3 sắp tới, bạn Nam Tuấn lớp 8A2 quyết định mua một bó hoa thật đẹp tặng cho Bảo Châu cùng lớp- 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. Tuấn đ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. Châu 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 Tuấn 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. Châu 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à Tuấn 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.

Tuấn quyết định sẽ tặng cho Châu 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à học sinh, không có nhiều tiền nên Tuấn 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 Tuấn 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 Châu (0 ≤ S ≤ 10⁹) và P là giá của mỗi đóa hoa (1 ≤ P ≤ 10⁶).

 - Dòng tiếp theo chứa N số nguyên dương A_i không vượt quát 10⁹ 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à Tuấn phải chi trả. Nếu không tìm ghép được bó hoa ưng ý thì xuất ra -1.

Ví dụ

      i  Input

 10 390 2
 200 10 20 20 50 50 50 50 100 100

   output

 10