Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
704 B
9
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define io(i) freopen("inp.inp","r",stdin);freopen("inp.out","w",stdout);
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int a[102],b[102],dp[102],vet[102],vet2[102];

void solve(){
	int n,s;cin>>n>>s;
	for (int i = 1;i<=n;i++) cin>>a[i]>>b[i];
	for (int i = 1;i<=n;i++)
		for (int j = a[i];j<=s;j++){
			if (dp[j] < dp[j-a[i]]+b[i]){
				dp[j] = dp[j-a[i]]+b[i];
				vet[j] = i;	
			}
		}
	cout<<dp[s]<<'\n';
	for (int j = s;j>0;j=j-a[vet[j]]) vet2[vet[j]]++;
	for (int i = 1;i<=102;i++) if (vet2[i]!=0) cout<<vet2[i]<<' '<<i<<'\n';
}
int main(){
	io(inp);fio
	int t = 1;
	while (t--){
		solve();
	}
	return 0;
}
Leave a Comment