[USACO06DEC]The Fewest Coins G

Title Description

Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is.

FJ wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, …, VN (1 ≤ Vi ≤ 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, …, and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change).

Farmer John I want to buy some supplies in town . In order to accomplish the task efficiently , He wanted to minimize the number of coin changes . Even if he delivers hard The number of coins and change is the least .

John Want to buy something worth T Things that are . Yes N(1<=n<=100) There are two kinds of money in circulation , The denominations are V1,V2…Vn (1<=Vi<=120).John Yes Ci The denomination is Vi The coin of (0<=Ci<=10000).

Let's assume that the owner has an unlimited number of coins , And always change according to the best plan . Note that there is no solution output -1.

Input format

Line 1: Two space-separated integers: N and T.

Line 2: N space-separated integers, respectively V1, V2, …, VN coins (V1, …VN)

Line 3: N space-separated integers, respectively C1, C2, …, CN

Output format

Line 1: A line containing a single integer, the minimum number of coins involved in a payment and change-making. If it is impossible for Farmer John to pay and receive exact change, output -1.

Examples #1

The sample input #1

3 70
5 25 50
5 2 1

Sample output #1

3

Tips

Farmer John pays 75 cents using a 50 cents and a 25 cents coin, and receives a 5 cents coin in change, for a total of 3 coins used in the transaction.

Obviously, the purchase is a multiple backpack （ Binary optimization and above ）, Change is a complete backpack , The only problem is to determine the biggest purchase $M$ .

Explanation of the problem $M=max(v[i{]}^2)$ I won't prove , I didn't understand , however , $M=\sum v[i]$ Is clearly established , Then run an enumeration .

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;

ll n,m;
struct good{
    
    int v,w;
};
vector<good>g;
int V[110],C[110],f[21000],dp[21000],mx;
void solve(){
    
    cin>>n>>m;
    memset(f,0x3f,sizeof f); // f[j] It means to buy j The minimum number of coins needed to pay for a value item  ,  Multiple backpack 
    memset(dp,0x3f,sizeof dp); //  Completely backpack 
    f[0] = 0;
    dp[0] = 0;
    fo(i,1,n)cin>>V[i],mx = max(mx,V[i]);
    mx *= mx;
    fo(i,1,n)cin>>C[i];
    fo(i,1,n){
    
        int s = C[i];
        for(int k=1;k<=C[i];k<<=1){
    
            g.pb({
    k*V[i],k});
            s-=k;
        }
        if(s>0){
    
            g.pb({
    s*V[i],s});
        }
    }
    
    for(auto c:g){
    
        for(int j=mx;j>=c.v;j--){
    // J  It's money 
            f[j] = min(f[j],f[j-c.v]+c.w);
        }
        for(int j=c.v;j<=mx;j++){
    
            dp[j] = min(dp[j],dp[j-c.v]+c.w);
        }
    }

    if(f[m] == 0x3f3f3f3f){
    
        puts("-1");
    }
    else{
    
        int ans = 0x3f3f3f3f;
        for(int i=m;i<=m+mx;i++){
    
            debug(i);
            ans = min(ans,f[i]+dp[i-m]);
        }
        if(ans == 0x3f3f3f3f)ans=-1;
        cout<<ans;
    }
}
int main(){
    
    solve();
    return 0;
}