chooseGoodsToWin

Trong ngày khai trương siêu thị mới của CL, siêu thị tổ chức một chương trình đặc biệt cho khách hàng như sau:

Trong siêu thị có n món hàng, mỗi món hàng thứ i sẽ có trọng lượng w[i] và có giá trị v[i]. Nếu khách hàng nào mua được các món hàng có tổng trọng lượng trong phạm vi [a, b] sẽ được tham gia chương trình khuyến mãi vô cùng hấp dẫn của CL. Ai là chủ nhân của lá thăm có tổng giá trị các hàng hóa lớn nhất, sẽ được mua hàng miễn phí trong một tháng.

Bảo cũng muốn tham gia, nhưng không biết cách chọn hàng hóa sao để thắng. Bạn hãy giúp Bảo giải quyết vấn đề, và trả về giá trị của lá thăm của Bảo nhé. Nếu không có cách nào chọn thì trả về -1

Ví dụ:

• Với n = 3, a = 6, b = 8, w = [3, 7, 8], v = [10, 3, 2] thì kết quả choose_goods_to_win(n, a, b, w, v) = 3.
  Giải thích:
  Bảo cần chọn món hàng có trọng lượng là 7..

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.1s với C++, 0.6s với Java và C#, 0.8s với Python, Go và JavaScript.

• [Đầu vào] integer n.
  1 ≤ n ≤ 32

• [Đầu vào] long a, b.
  1 ≤ a, b ≤ 1016

• [Đầu vào] array of long w, v.
  1 ≤ w[i], v[i] ≤ 1015

• [Đầu ra] long.
  Trả về giá trị của chiếc lá thăm chiến thắng của Bảo