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<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back 
#define pf push_front 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define All(v) v.begin(),v.end()

typedef pair<int, int> Pii; typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;

int N, M, K;
vector<Pii> ab;
int a[16], b[16];
int dp[16][10001][16];

int dfs(int n, int m, int k) {
  if ( n == N || k == K || m == 0 ) return m;
  if ( dp[n][m][k] >= 0 ) return dp[n][m][k];

  int a = ab[n].fr, b = ab[n].sc;
  return dp[n][m][k] = max(dfs(n+1, max(0LL, m-b), k+1) + min(m, b)*a, dfs(n+1, m, k));
}

signed main() {
  memset(dp, -1, sizeof(dp));
  cin >> N >> M >> K;
  Rep(i, N) cin >> a[i];
  Rep(i, N) cin >> b[i];
 
  Rep(i, N) {
    ab.pb(Pii(a[i], b[i]));
  }
  
  sort(All(ab), greater<Pii>());

  cout << dfs(0, M, 0) << endl;
  
  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<utility>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef pair<int,int> p;
typedef long long ll;

ll max(ll a,ll b){
	return (a>b)?a:b;
}

ll min(ll a,ll b){
	return (a>b)?b:a;
}

int main(){
	ll n,m,k;
	cin>>n>>m>>k;
	ll a[n],b[n];
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	ll ans=0;
	if(n==1){
		rep(i,n)ans=max(ans,a[i]*min(m,b[i])+max(0,m-b[i]));
	}else if(n==2){
		rep(i,n){
			rep(j,n){
				rep(j,n){
					if(i==j)continue;
					ans=max(ans,a[i]*min(m,b[i])+a[j]*min(m-b[i],b[j])+max(0,m-b[i]-b[j]));
				}
			}
		}
	}else{
		rep(i,n){
			rep(j,n){
				rep(k,n){
					if((i==j) || (j==k) || (k==i))continue;
					ans=max(ans,a[i]*min(m,b[i])+a[j]*min(m-b[i],b[j])+a[k]*min(m-b[i]-b[j],b[k])+max(0,m-b[i]-b[j]-b[k]));
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

C++: #include<iostream>
#include<bits/stdc++.h>
#define MAX 100;

using namespace std;
int N,M,K;
int a[20];
int b[20];

typedef pair<int,int> ii;

void input(){
  cin>>N>>M>>K;
  
  vector<ii> vec(N);
  for(int i=0;i<N;i++){
    cin>>a[i];
    vec[i].first = a[i];
  }
  for(int i=0;i<N;i++){
    cin>>b[i];
    vec[i].second = b[i];
  }
  sort(vec.begin(),vec.end());
  for(int i=0;i<N;++i) {
    a[i] = vec[i].first;
    b[i] = vec[i].second;
  }
}
int field[3];
int array[100000];
int main(){
  int spa=0;
  input();
  for(int k=0;k<N;k++){
    for(int l=k+1;l<N;l++){
      for(int m=l+1;m<N;m++){
	int ans=0;
	int las_Imo=M;
	field[0]=k;
	field[1]=l;
	field[2]=m;
	for(int i=2;i>=0;i--){
	  for(int t=0;t<b[field[i]];t++){
	    las_Imo--;
	    if(las_Imo<0) break;
	    ans=ans+a[field[i]];
	  }
	   
	}
	
	ans = ans + (las_Imo>=0?las_Imo:0);
	array[spa++]=ans;
      }
    }
  }
  sort(array,array+100000,greater<int>());
  cout<<array[0]<<endl;			
  return 0;
}

C++: #include <iostream>
using namespace std;

typedef struct {
    int a,b;
}poteinfo;

int main(){
    int a,b,c,n,m,tm,k,t,maxc;
    poteinfo pi[15];
    
    cin >> n >> m >> k;
    
    for (int i=0;i<n;i++) cin >> pi[i].a;
    for (int i=0;i<n;i++) cin >> pi[i].b;
    
    maxc=m;
    
    if (n==1) {
        t=0;
        tm=m;
        if (pi[a].b<=tm){
            t+=pi[a].a*pi[a].b;
            tm-=pi[a].b;
        }
        t+=tm;
        if (maxc < t) maxc=t;
    }else if(n==2){
        for (a=0;a<n;a++){
            for (b=0;b<n;b++){
                t=0;
                tm=m;
                if (pi[a].b<=tm){
                    t+=pi[a].a*pi[a].b;
                    tm-=pi[a].b;
                }
                if (k>=2) {
                    if (a!=b && pi[b].b<=tm){
                        t+=pi[b].a*pi[b].b;
                        tm-=pi[b].b;
                    }
                }
                t+=tm;
                if (maxc < t) maxc=t;
            }
        }

    }else{
        for (a=0;a<n;a++){
            for (b=0;b<n;b++){
                for (c=0;c<n;c++){
                    t=0;
                    tm=m;
                    if (pi[a].b<=tm){
                        t+=pi[a].a*pi[a].b;
                        tm-=pi[a].b;
                    }
                    if (k>=2) {
                        if (a!=b && pi[b].b<=tm){
                            t+=pi[b].a*pi[b].b;
                            tm-=pi[b].b;
                        }
                    }
                    if (k>=3) {
                        if (a!=c && b!=c && pi[c].b<=tm){
                            t+=pi[c].a*pi[c].b;
                            tm-=pi[c].b;
                        }
                    }
                    t+=tm;
                    if (maxc < t) maxc=t;
                }
            }
        }
    }
    
    cout << maxc << endl;
    
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int n,m,k,ans=0;
typedef pair<int,int> P;
vector<P> v;
int rec(int x,int y,int z){//x=imo;y=men;z=mensuu
  int res=0,i,j;
  if(z==k) return m-x;
  for(i=y;i<n;i++){
    j=min(v[i].second,m-x);
    res=max(res,v[i].first*j+rec(x+j,i+1,z+1));
  }
  return res;
}
int main(){
  int i,j;
  cin>>n>>m>>k;
  v.resize(n);
  for(i=0;i<n;i++) cin>>v[i].first;
  for(i=0;i<n;i++) cin>>v[i].second;
  sort(v.begin(),v.end(),greater<P>());
  cout << rec(0,0,0) << endl;
  return 0;
}