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 rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto&& x : v){cout << x << " ";} cout << endl
#define printVV(vv) for(auto&& v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto&& p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;
template<typename T> using Graph = vector<vector<T>>;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N, M, K;
    cin >> N >> M >> K;
    vi a(N), b(N);
    rep(i, N) cin >> a[i];
    rep(i, N) cin >> b[i];

    int ans = -1;
    rep(s, 1 << N) {
        if (__builtin_popcount(s) != K) {
            continue;
        }
        vector<Pii> vp;
        rep(i, N) {
            if ((s >> i) & 1) {
                vp.emplace_back(a[i], b[i]);
            }
        }
        sort(all(vp));
        reverse(all(vp));
        int tmp = 0;
        int res = M;
        for (auto p : vp) {
            int a, b;
            tie(a, b) = p;
            tmp += a * min(res, b);
            res -= min(res, b);
        }
        ans = max(ans, tmp + res);
    }
    cout << ans << endl;
}

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

int main()
{
  int n,m,k;
  pair<int,int> p[20];
  int a,b,c;
  int i,j,l;

  cin>>n>>m>>k;

  for(i=0;i<n;i++)
    cin>>p[i].first;
  for(i=0;i<n;i++)
    cin>>p[i].second;

  sort(p,p+n);

  if(k==1){
    a=min(m,p[n-1].second);
    cout<<p[n-1].first*a+m-a<<endl;;

  }else if(k==2){ 

    int dp[20][20]={};
    int ans=0;
    for(i=0 ; i<n-1 ; i++)
      for(j=i+1 ; j<n ; j++){
	a=min(p[j].second,m);
	b=min(p[i].second,m-a);
	dp[i][j]=p[j].first*a+p[i].first*b;
	ans=max(ans,dp[i][j]+m-a-b);
      }
    cout<<ans<<endl;


  }else if(k==3){

    int dp[20][20][20]={};
    int ans=0;

    for(i=0;i<n-2;i++)
      for(j=i+1;j<n-1;j++)
	for(l=j+1;l<n;l++){
	  a=min(p[l].second,m);
	  b=min(p[j].second,m-a);
	  c=min(p[i].second,m-a-b);
	  dp[i][j][l]=p[l].first*a+p[j].first*b+p[i].first*c;
	  ans=max(ans,dp[i][j][l]+m-a-b-c);

	}

    cout<<ans<<endl;
  }

}

C++: #include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;

void inputData(int n, vector< pair<int, int> > &vp){
    int a[20], b[20];
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    rep(i, n) vp.push_back(make_pair(a[i], b[i]));
    sort(all(vp), greater< pair<int, int> >());
}

int main(){
    int ans = 0;
    int n, m, k;
    vector< pair<int, int> > vp;
    cin >> n >> m >> k;
    inputData(n, vp);

    //rep(i,n) cout << vp[i].first << endl;

    //bit??§??¨??????
    rep(i, (1 << n)){
        //????????????k?????\???????????????????????????????????????
        int c = 0; 
        rep(j, n) if( (i & (1 << j)) == (1 << j) ) c++;
        if(c > k) continue;

        //??¨??????
        int imo = m, sum = 0;
        rep(j, n){
            if( (i & (1 << j)) == (1 << j) ){
                if(vp[j].second <= imo){ //???????????§???????????????????????´???
                    imo -= vp[j].second;
                    sum += vp[j].first * vp[j].second;
                }else{
                    sum += vp[j].first * imo;
                    imo = 0;
                }
            }
        }
        ans = max(ans, sum + imo);
    }
    cout << ans << endl;
}

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

int main()
{
  int n,m,k;
  pair<int,int> p[20];
  int a,b,c;
  int i,j,l;

  cin>>n>>m>>k;

  for(i=0;i<n;i++)
    cin>>p[i].first;
  for(i=0;i<n;i++)
    cin>>p[i].second;

  sort(p,p+n);

  if(k==1){
    int ans=0;
    for(i=0;i<n;i++){
    a=min(m,p[i].second);
    ans=max(ans,p[i].first*a+m-a);
    }
    cout<<ans<<endl;

  }else if(k==2){ 

    long long dp[20][20]={};
    long long ans=0;
    for(i=0;i<n-1;i++)
      for(j=i+1;j<n;j++){
	a=min(p[j].second,m);
	b=min(p[i].second,m-a);
	dp[i][j]=p[j].first*a+p[i].first*b;
	ans=max(ans,dp[i][j]+m-a-b);
      }
    cout<<ans<<endl;


  }else if(k==3){

    long long dp[20][20][20]={};
    long long ans=0;

    for(i=0;i<n-2;i++)
      for(j=i+1;j<n-1;j++)
	for(l=j+1;l<n;l++){
	  a=min(p[l].second,m);
	  b=min(p[j].second,m-a);
	  c=min(p[i].second,m-a-b);
	  dp[i][j][l]=p[l].first*a+p[j].first*b+p[i].first*c;
	  ans=max(ans,dp[i][j][l]+m-a-b-c);

	}

    cout<<ans<<endl;
  }

}