Go: package main

import (
    "bufio"
    "os"
    "fmt"
    "strings"
    "strconv"
    "sort"
    "math"
)

/************** Input *************/
var sc = bufio.NewScanner(os.Stdin)

func ReadLineToInt () []int{
    sc.Scan()
    line := strings.Split(sc.Text(), " ")
    length := len(line)
    var intLine []int
    for i := 0;i < length; i++ {
        n, _ := strconv.Atoi(line[i])
        intLine = append(intLine, n)
    }
    return intLine
}

/************* Pairs **************/
type Pair struct {
    a int
    b int
}

type SortablePairs struct {
    arr []*Pair
    lessfunc []lessFunc
}

type lessFunc func(p *Pair, q *Pair)bool

func (sp SortablePairs) Len() int {
    return len(sp.arr)
}

func (sp SortablePairs) Swap(i ,j int) {
    sp.arr[i], sp.arr[j] = sp.arr[j], sp.arr[i]
}

func (sp SortablePairs) Less(i, j int) bool {
    p, q := sp.arr[i], sp.arr[j]
    for k := 0; k < len(sp.lessfunc); k++ {
        less := sp.lessfunc[k]
        if less(p, q) {
            return true
        } else if less(q, p) {
            return false
        }
    }
    return false
}

/***********  min, max  *************/
func min(a, b int) int {
    return int(math.Min(float64(a), float64(b)))
}

func max(a, b int) int {
    return int(math.Max(float64(a), float64(b)))
}


/************  main  ***************/
func main() {
    nmk := ReadLineToInt()
    n, m, k := nmk[0], nmk[1], nmk[2]
    aSlice := ReadLineToInt()
    bSlice := ReadLineToInt()
    sp := SortablePairs{}
    for i := 0; i < n; i++ {
        sp.arr = append(sp.arr, &Pair{a: aSlice[i], b: bSlice[i]})
    }

    sortFunc := func(p, q *Pair) bool {
        return p.a > q.a
    }

    sp.lessfunc = append(sp.lessfunc, sortFunc)
    sort.Sort(sp)

    var dp [4][10001]int
    for i := 0; i < n; i++ {
        item := sp.arr[i]
        a := item.a
        b := item.b
        for y := k - 1;y >= 0; y-- {
            for x := m - 1; x >= 0; x-- {
                use := min(b, m - x)
                dp[y + 1][x + use] = max(dp[y + 1][x + use], dp[y][x] + use * a)
            }
        }
    }
    var ans int
    for y := 0; y <= k; y++ {
        for x := 0; x <= m; x++ {
            ans = max(ans, dp[y][x] + m - x)
        }
    }
    fmt.Println(ans)
}

C++: #define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<pair<int, int> > v(n);
    for(int i=0; i<n; ++i)
        cin >> v[i].first;
    for(int i=0; i<n; ++i)
        cin >> v[i].second;
    sort(v.rbegin(), v.rend());

    int ans = 0;
    for(int j=0; j<(1<<n); ++j){
        bitset<15> bs(j);
        if(k < bs.count())
            continue;

        int rest = m;
        int cnt = 0;
        for(int i=0; i<n; ++i){
            if(bs[i]){
                int x = min(rest, v[i].second);
                cnt += v[i].first * x;
                rest -= x;
            }
        }
        ans = max(ans, cnt + rest);
    }
    cout << ans << endl;

    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int n,m,k;
int a[15],b[15];

ll dp[4][16][10010];
ll dfs(int num, int x, int rem)
{
    if(num==k) return rem;
    if(dp[num][x][rem]>=0) return dp[num][x][rem];

    ll ret = rem;
    for(int i=x; i<n; ++i)
    {
        rep(j,min(b[i],rem)+1) ret = max(ret,dfs(num+1,i+1,rem-j)+(ll)a[i]*j);
    }

    return dp[num][x][rem] = ret;
}

int main()
{
    cin >>n >>m >>k;
    rep(i,n) cin >>a[i];
    rep(i,n) cin >>b[i];

    memset(dp,-1,sizeof(dp));
    cout << dfs(0,0,m) << endl;;
    return 0;
}

C++: #include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define stop char nyaa;cin>>nyaa;

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<pair<int,int>> p(n);
	rep(i, n) cin >> p[i].first;
	rep(i, n) cin >> p[i].second;
	vector<int> c(n,0);
	rep(i, k) c[n-i-1] = 1;
	int ans = 0;
	do {
		vector<pair<int, int>> v;
		rep(i, n) if (c[i]) v.push_back(p[i]);
		sort(v.begin(), v.end(), greater<pair<int, int>>());
		int tmp = 0;
		int x = m;
		for (int i = 0; i < v.size(); i++) {
			if (v[i].second >= x) {
				tmp += x * v[i].first;
				x = 0;
				break;
			}
			else {
				tmp += v[i].second * v[i].first;
				x -= v[i].second;
			}
		}
		ans = max(ans, tmp+x);
	} while (next_permutation(c.begin(), c.end()));
	cout << ans << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	stop
		return 0;
}

C++: #include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int N; int M; int K;
	while(~scanf("%d%d%d", &N, &M, &K)) {
		vector<int> a(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &a[i]);
		vector<int> b(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &b[i]);
		vpii ab;
		int ans = 0;
		rep(s, 1 << N) {
			ab.clear();
			rep(i, N) if(s >> i & 1) {
				ab.emplace_back(-a[i], b[i]);
			}
			if((int)ab.size() > K) continue;
			sort(ab.begin(), ab.end());
			int rem = M, sum = 0;
			for(auto p : ab) {
				int num = min(rem, p.second);
				sum += num * -p.first;
				rem -= num;
			}
			sum += rem;
			amax(ans, sum);
		}
		printf("%d\n", ans);
	}
	return 0;
}