Duyệt hết tất cả các đội hình tiêu diệt được quái vật. Với mỗi đội hình đó, duyệt từng quân lính có trong đội hình. Nếu bỏ quân lính đó đi và giữ nguyên các quân lính còn lại, đội hình đó không tiêu diệt quái vật được nữa thì đánh dấu quân lính đó là quan trọng. Với một quân lính \(i\), nếu sau khi duyệt hết tất cả các đội hình thoả mãn mà quân lính đó không được đánh dấu thì quân lính đó không quan trọng.
Độ phức tạp: \(\mathcal{O}(2^n \times n)\).

Với mỗi quân lính \(i\), ta sẽ tìm đội hình có tổng sức mạnh lớn nhất nhỏ hơn \(k\) mà không chứa quân lính thứ \(i\), nếu tổng sức mạnh của đội hình đó cộng với sức mạnh của quân lính thứ \(i\) lớn hơn hoặc bằng \(k\) thì quân lính đó quan trọng. Ngược lại quân lính đó không quan trọng bởi vì nếu quân lính thứ \(i\) quan trọng thì tức là đội hình tìm được chưa phải là đội hình có tổng sức mạnh lớn nhất mà nhỏ hơn \(k\).
Để tìm được đội hình có tổng sức mạnh lớn nhất nhỏ hơn \(k\) mà không chứa quân lính thứ \(i\), ta sử dụng kỹ thuật quy hoạch động cái túi để giải quyết bài toán này (không xét quân lính thứ \(i\)).
Độ phức tạp: \(\mathcal{O}(n^2 \times k)\)

Ở subtask này, ta sẽ thay đổi thuật toán ở subtask 2 một chút. Thay vì với mỗi quân lính thứ \(i\) tìm đội hình có tổng sức mạnh lớn nhất nhỏ hơn \(k\) mà không chứa quân lính thứ \(i\), ta chỉ cần kiểm tra liệu có tồn tại một đội hình (không chứa quân lính thứ \(i\)) nào có tổng sức mạnh nằm trong đoạn \([k-p_i, \ k-1]\). Bởi vì nếu tồn tại một đội hình như thế, đội hình đó nếu không có quân lính thứ \(i\) thì không tiêu diệt được quái vật, nhưng nếu thêm vào thì sẽ tiêu diệt được quái vật.
Giả sử tồn tại một đội hình như thế, ta có thể tách đội hình ra làm hai tập, tập thứ nhất là tập các quân lính có sức mạnh nhỏ hơn \(p_i\), tập thứ hai là tập các quân lính có sức mạnh lớn hơn hoặc bằng \(p_i\). Thay tập thứ hai thành tập các quân lính có sức mạnh lớn hơn hoặc bằng \(p_i\) và tập đó là tập có tổng sức mạnh lớn nhất nhỏ hơn \(k\).
Tổng sức mạnh của đội hình mới \(\geq k - p_i\). Nếu như tổng sức mạnh của đội hình mới đó \(> k\) thì ta có thể loại bớt đi các quân lính thuộc tập thứ nhất. Ta hoàn toàn có thể chứng minh được rằng bằng cách loại đi không hoặc một số quân lính ở tập thứ nhất, ta sẽ tạo ra được một đội hình có tổng sức mạnh nằm trong đoạn \([k-p_i, \ k-1]\).
Từ đó ta có thể nghĩ ra được một ý tưởng đó là với mỗi quân lính thứ \(i\), ta tìm tập các quân lính không chứa nó có sức mạnh \(\geq p_i\) sao cho tổng sức mạnh là lớn nhất nhưng vẫn nhỏ hơn \(k\). Sau đó cộng thêm vào sức mạnh của tất cả các quân lính có sức mạnh \(< p_i\). Nếu như tổng sức mạnh khi ấy \(\geq k-p_i\) thì quân lính thứ \(i\) là quan trọng.
Để làm được điều này, ta có thể sắp xếp các quân lính theo thứ tự chỉ số sức mạnh giảm dần, rồi duyệt từ quân lính có sức mạnh lớn nhất (từ \(1\) đến \(n\)). Sử dụng kỹ thuật quy hoạch động cái túi để tìm ra được đội hình có tổng sức mạnh lớn nhất nhỏ hơn \(k\) khi chỉ xét các quân lính từ \(1\) đến \(i-1\). Lấy giá trị đó cộng cho \(\displaystyle\sum_{j=i+1}^{n}{p_j}\). Nếu tổng đó \(\geq k-p_i\) thì quân lính thứ \(i\) là quan trọng. Ngược lại thì không quan trọng.
Độ phức tạp: \((n \times k)\).

Liệu bạn có thể giải bài này với \(n, k \leq 5 \cdot 10^4\)?