Tóm tắt đề bài

Cho ~n~ món đồ, món đồ thứ ~i~ có giá mua là ~c_i~ và giá trị là ~v_i~. Tuy vậy, có ~k~ điều kiện dạng ~(a_i, b_i)~ có nghĩa: nếu bạn mua món đồ ~a_i~, bạn phải mua món đồ ~b_i~.

Với số tiền ~m~ đồng, hãy mua các món đồ sao cho tổng giá trị là lớn nhất.

Giới hạn: ~n \le 1000~, ~k \le 10^4~, ~m, c_i, v_i \le 10^9~

Subtask 1: ~c_i, m \le 1000~, ~k \le 2~

Với một điều kiện ~(a_i, b_i)~ có bốn cách chọn:

• Không mua cả hai: hợp lệ.
• Mua cả hai: hợp lệ.
• Mua ~a_i~, không mua ~b_i~: Không hợp lệ.
• Không mua ~a_i~, mua ~b_i~: Hợp lệ.

Vì vậy, với mỗi điều kiện, ta có ba cách chọn. Ta sẽ duyệt ~3^k~ cách chọn này.

Ta cần kiểm tra các lựa chọn có mâu thuẫn nhau không. Nói cách khác, chẳng hạn nếu ở điều kiện ~1~ ta phải mua vật ~x~, nhưng ở điều kiện ~2~ ta lại không mua vật ~x~, thì đây là mâu thuẫn.

Sau khi có danh sách các vật phải mua, và các vật không được mua, ta có thể quy hoạch động cái túi như bình thường, do giới hạn ~n \times m \le 10^6~ khá nhỏ.

Độ phức tạp: ~O~ (~3^k \times n \times m~).

Subtask 2: ~n \le 20~.

Với subtask này, ta hoàn toàn có thể duyệt mọi tập con của ~n~ phần tử. Sau đó, ta cần kiểm tra tập con này có thỏa mãn không.

Trước hết, ta cần kiểm tra tập con này có thỏa mãn ~k~ điều kiện nói trên không. Có thể duyệt đủ ~k~ điều kiện, tuy nhiên điều này là khá chậm. Ta có thể làm cách khác:

• Với mỗi điều kiện ~i~, ta sẽ lưu các vật phẩm phải mua nếu mua vật phẩm thứ ~i~ dưới dạng bitmask.
• Sau đó, ta có thể dễ dàng kiểm tra bằng phép toán AND hai tập hợp. Gọi ~mask~ là tập con của ~n~ phần tử ta đang thử, ~must~ là tập các vật phẩm phải mua khi mua vật phẩm ~i~ (mà vật phẩm ~i~ cũng phải nằm trong ~mask~), thì tập này thỏa mãn nếu ~mask~ ~\&~ ~must = must~.

Sau đó, ta cần tính tổng số tiền phải trả cho tập con này, nếu ~\le m~ thì ta cập nhật vào kết quả.

Độ phức tạp: ~O~ ~(2^n \times n)~.