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++: #include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	bool operator<(const struct Info &arg) const{
		return mult < arg.mult;
	};
	int mult,can_plant;
};

int main(){

	int N,M,K;
	scanf("%d %d %d",&N,&M,&K);

	Info info[N];

	for(int i = 0; i < N; i++){
		scanf("%d",&info[i].mult);
	}

	for(int i = 0; i < N; i++){
		scanf("%d",&info[i].can_plant);
	}

	int ans = M;

	int limit = pow(2,N);

	vector<int> V;

	priority_queue<Info> Q;

	for(int i = 0; i < limit; i++){
		V.clear();
		for(int loop = 0; loop < N; loop++){
			if(i & (1 << loop)){
				V.push_back(loop);
			}
		}
		if((int)V.size() > K)continue;

		for(int a = 0; a < V.size(); a++){
			Q.push(info[V[a]]);
		}

		int sum = 0;
		int rest = M;

		while(!Q.empty()){

			if(rest >= Q.top().can_plant){

				rest -= Q.top().can_plant;
				sum += Q.top().can_plant*Q.top().mult;

			}else{ //rest < Q.top().can_plant
				sum += rest*Q.top().mult;
				rest = 0;
			}
			Q.pop();
		}

		sum += rest;

		ans = max(ans,sum);
	}

	printf("%d\n",ans);

	return 0;
}

C++: #include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

template < class BidirectionalIterator >
bool next_combination(BidirectionalIterator first1,
	BidirectionalIterator last1,
	BidirectionalIterator first2,
	BidirectionalIterator last2)
{
	if ((first1 == last1) || (first2 == last2)) {
		return false;
	}
	BidirectionalIterator m1 = last1;
	BidirectionalIterator m2 = last2; --m2;
	while (--m1 != first1 && !(*m1 < *m2)) {
	}
	bool result = (m1 == first1) && !(*first1 < *m2);
	if (!result) {
		// ???
		while (first2 != m2 && !(*m1 < *first2)) {
			++first2;
		}
		first1 = m1;
		std::iter_swap(first1, first2);
		++first1;
		++first2;
	}
	if ((first1 != last1) && (first2 != last2)) {
		// ???
		m1 = last1; m2 = first2;
		while ((m1 != first1) && (m2 != last2)) {
			std::iter_swap(--m1, m2);
			++m2;
		}
		// ??¢
		std::reverse(first1, m1);
		std::reverse(first1, last1);
		std::reverse(m2, last2);
		std::reverse(first2, last2);
	}
	return !result;
}

template < class BidirectionalIterator >
bool next_combination(BidirectionalIterator first,
	BidirectionalIterator middle,
	BidirectionalIterator last)
{
	return next_combination(first, middle, middle, last);
}

int main() {
	int N,M,K;cin>>N>>M>>K;
	vector<int>as(N),bs(N);
	for (int i = 0; i < N; ++i) {
		cin>>as[i];
	}
	for (int j = 0; j < N; ++j) {
		cin>>bs[j];
	}
	vector<int>perms(N);
	iota(perms.begin(),perms.end(),0);
	int ans=0;
	do {
		do {
			int nans=0;
			int rest(M);
			for (int i = 0; i < K; ++i) {
				int use=min(rest,bs[perms[i]]);
				nans+=use*as[perms[i]];
				rest-=use;
			}
			nans+=rest;
			ans=max(ans,nans);
		}while(next_permutation(perms.begin(),perms.begin()+K));
	}while(next_combination(perms.begin(),perms.begin()+K,perms.end()));
	cout<<ans<<endl;
	return 0;
}

C++: #include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef pair<int,int>P;

int n,m,k,a[111],b[111],ans;

void dfs(int d,int sum,vector<int> v){
  if(sum>k)return;
  if(d==n){
    vector<P>V;
    r(i,v.size())V.push_back(P(a[v[i]],b[v[i]]));
    sort(V.begin(),V.end(),greater<P>());
    int N=m,cnt=0;
    r(i,V.size()){
      if(N<=0)break;
      int cost=V[i].first;
      int lim=V[i].second;
      int x=min(N,lim);
      cnt+=x*cost;
      N-=lim;
    }
    ans=max(ans,cnt+max(N,0));
  }
  else{
    dfs(d+1,sum,v);
    v.push_back(d);
    dfs(d+1,sum+1,v);
  }
}

int main(){
  cin>>n>>m>>k;
  r(i,n)cin>>a[i];
  r(i,n)cin>>b[i];
  vector<int>v;
  dfs(0,0,v);
  cout<<ans<<endl;
}

C++: #include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back
#define ALL(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef int ut;
typedef pair<ut,ut> pr;
typedef vector<ut> VI;
typedef vector<pr> Vpr;
const int SIZE=100;
Vpr ab;
int a[SIZE],b[SIZE];
int N,M,K;
int solve(int now,int able,int m){
	int ans=0;
	if(now==N) return m;
	if(able){
		int used=min(m,ab[now].second);
	    int getP=used*ab[now].first;
		ans=solve(now+1,able-1,m-used)+getP;
	//	cout << getP << endl;
	}
	return max(solve(now+1,able,m),ans);
}
int main(){
	
	cin >> N >> M >> K;
	REP(i,N){
		cin >> a[i];
	}
	REP(i,N){
		cin >> b[i];
	}
	REP(i,N){
		ab.PB(pr(a[i],b[i]));
	}
	sort(ALL(ab),greater<pr>());
	cout << solve(0,3,M) << endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <sstream>
#include <string>
#include <complex>
#include <cstdio>
using namespace std;

pair<int,int> a[15];

int main(){
	int n,m,K;
	cin >> n >> m >> K;
	for(int i = 0 ; i < n ; i++) cin >> a[i].first;
	for(int i = 0 ; i < n ; i++) cin >> a[i].second;
	long long w = 0;
	for(int k = 0 ; k < (1<<n) ; k++){
		if( __builtin_popcount(k) > K ) continue;
		vector<int> v;
		for(int i = 0 ; i < n ; i++){
			if( k >> i & 1 )
			for(int j = 0 ; j < a[i].second ; j++)
				v.push_back(a[i].first);
		}
		sort(v.rbegin(),v.rend());

		long long s = 0;
		for(int i = 0 ; i < min<int>(v.size(),m) ; i++){
			//cout << v[i] << endl;
			s += v[i];
		}
		w = max(w,s);

	}
	cout << w << endl;
}