个人感觉不如刷题大军

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005], b[100005], dp[100005];
int find(int left, int right, int val){
	if(dp[left] >= val) return left;
	if(dp[right] < val) return 0x3f3f3f3f;
	int mid = (left + right) >> 1;
	return min(find(left, mid, val), find(mid + 1, right, val));
}
int main(){
	int n, m, k;
	cin >> m >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = k; j >= b[i]; j--){
			dp[j] = max(dp[j - b[i]] + a[i], dp[j]);
		}
	}
	if(dp[k] < m) cout << "Impossible";
	else cout << k - find(1, k, m);

	return 0;
}