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<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();
  int maxi = 0;
  if( N == 1 ) {
    for(int k=0;k<N;k++){
      int ans=0;
      int las_Imo=M;
      field[0]=k;
      for(int i=0;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);
      maxi = max(maxi,ans);
    }
  } else if( N == 2 ) {
    for(int k=0;k<N;k++){
      for(int l=k+1;l<N;l++){
	int ans=0;
	int las_Imo=M;
	field[0]=k;
	field[1]=l;
	for(int i=1;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);
	maxi = max(maxi,ans);
      }
    }
  } else {
    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;
	  maxi = max(maxi,ans);
	}
      }
    }
  }
  //sort(array,array+100000,greater<int>());
  //cout<<array[0]<<endl;			
  cout << maxi << endl;
  return 0;
}

C++: #include<bits/stdc++.h>
#define int long long int
using namespace std;

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

int ah[4];
int ans = 0;
int bfs(int times)
{
  int ret = 0;
  if(times < k){
    for(int i = 1; i <= n; i++){
      ah[times] = i;
      ret = max(ret, bfs(times + 1));
    }
  }

  else{
    for(int i = 1; i < k; i++){
      if(ah[0] == ah[i]){
	return 0;
      }
    }
    if(k == 3 && ah[1] == ah[2]){
      return 0;
    }
    int remain = m;
    for(int i = 0; i < k; i++){
      ret += a[ah[i]] * min(remain, b[ah[i]]);
      remain = remain <= b[ah[i]] ? 0 : remain - b[ah[i]];
    }
    ret += remain;
  }
  return ret;
}

signed main()
{
  cin >> n >> m >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    cin >> b[i];
  }

  cout << bfs(0) << 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();
  int maxi = M;
  if( K == 1 ) {
    for(int k=0;k<N;k++){
      int ans=0;
      int las_Imo=M;
      field[0]=k;
      for(int i=0;i>=0;i--){
	for(int t=0;t<b[field[i]];t++){
	  if( las_Imo ) {
	    las_Imo--;
	    ans=ans+a[field[i]];
	  }
	}
      }
      ans = ans + ((las_Imo>=0)?las_Imo:0);
      maxi = max(maxi,ans);
    }
  } else if( K == 2 ) {
    for(int k=0;k<N;k++){
      for(int l=k+1;l<N;l++){
	int ans=0;
	int las_Imo=M;
	field[0]=k;
	field[1]=l;
	for(int i=1;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);
	maxi = max(maxi,ans);
      }
    }
  } else {
    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;
	  maxi = max(maxi,ans);
	}
      }
    }
  }
  //sort(array,array+100000,greater<int>());
  //cout<<array[0]<<endl;			
  cout << maxi << endl;
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M,K;
int ans;
int A[15],B[15];
vint vec;
void dfs(int n,int k){
    if(n==N){
        vint v=vec;
        rep(i,v.size()){
            for(int j=i+1;j<v.size();j++){
                if(A[v[i]]<A[v[j]])swap(v[i],v[j]);
            }
        }
        int cur=M;
        int sum=0;
        rep(i,v.size()){
            sum+=min(cur,B[v[i]])*A[v[i]];
            cur-=min(cur,B[v[i]]);
        }
        sum+=cur;
        chmax(ans,sum);
        return;
    }

    dfs(n+1,k);
    if(k<K){
        vec.pb(n);
        dfs(n+1,k+1);
        vec.pop_back();
    }
}
signed main(){
    cin>>N>>M>>K;
    rep(i,N)cin>>A[i];
    rep(i,N)cin>>B[i];

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