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>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

struct Edge {
  int dst;
  ll w;
};

struct Data {
  int cur;
  ll w;
  bool operator < ( const Data &data ) const {
    if( w != data.w ) return w < data.w;
    return cur < data.cur;
  }
};

const int MAX_V = 100010;

int V,E;
vector<Edge> G[MAX_V],rG[MAX_V];
ll maxi[MAX_V];
bool valid[MAX_V];
map<int,set<int> > mp;

bool check(ll limit) {
  memset(maxi,-1,sizeof maxi);
  priority_queue<Data> Q;
  /*
  for(set<int>::iterator itr=mp[limit].begin();itr!=mp[limit].end();itr++) {
    maxi[*itr] = limit;
    Q.push((Data){*itr,limit});
  }
  */
  rep(i,(int)G[V-1].size()) {
    if( G[V-1][i].w < limit ) continue;
    maxi[G[V-1][i].dst] = G[V-1][i].w;
    Q.push((Data){G[V-1][i].dst,G[V-1][i].w});
  }
  while( !Q.empty() ) {
    Data data = Q.top(); Q.pop();
    if( data.cur == 0 ) {
      return true;
    }
    rep(i,(int)G[data.cur].size()) {
      Edge &e = G[data.cur][i];
      if( e.dst == V-1 ) continue;
      if( !valid[e.dst] ) continue;
      if( !( data.w >= e.w ) )  continue;
      if( maxi[e.dst] < e.w ) {
	maxi[e.dst] = e.w;
	Q.push((Data){e.dst,e.w});
      }
    }
  }
  return false;
}


void pre_calc() {
  memset(valid,false,sizeof valid);
  deque<int> deq;
  deq.push_back(0);
  valid[0] = valid[V-1] = true;
  while( !deq.empty() ) {
    int cur = deq.front(); deq.pop_front();
    if( cur == V-1 ) continue;
    rep(i,(int)rG[cur].size()) {
      int next = rG[cur][i].dst;
      if( !valid[next] ) {
	valid[next] = true;
	deq.push_back(next);
      }
    }
  }
}


void compute() {
  pre_calc();
  vector<ll> vec;

  rep(i,(int)G[V-1].size()) {
    if( valid[G[V-1][i].dst] ) {
      vec.push_back(G[V-1][i].w);
    }
  }
  if( vec.empty() ) {
    puts("-1");
    return;
  }
  sort(vec.begin(),vec.end());
  int L = 0, R = (int)vec.size();
  while( R - L ) {
    int M = ( L + R ) / 2;
    if( check(vec[M]) ) L = M + 1;
    else                R = M;
  }
  if( L-1 < 0 ) {
    puts("-1");
  } else {
    cout << vec[L-1] << endl;
  }
}

int main() {
  cin >> V >> E;
  rep(i,E) {
    int a,b,c;
    cin >> a >> b >> c;
    --a, --b;
    G[b].push_back((Edge){a,c});
    rG[a].push_back((Edge){b,c});
  }
  compute();
  return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define int long long

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int a[20], b[20];

signed main()
{ // #define int long long ?????????????????§scanf???????????¨???????????????????????\?????????????????????
    int N, M, K; cin >> N >> M >> K;

    rep(i, N) cin >> a[i];
    rep(i, N) cin >> b[i];

    int ma = 0;

    rep(bit, 1<<N) {
        int cnt = 0;
        vpii choice;
        rep(i, N) {
            if (bit >> i & 1) cnt += 1, choice.PB(pii(a[i], b[i]));
        }

        if  (cnt != K) continue;

        sort(all(choice), greater<pii>());

        int sum = 0;

        int m = M;

        rep(i, K) {
            sum += choice[i].fst * min(m, choice[i].scd);
            m -= min(m, choice[i].scd);
        }

        sum += m;

        chmax(ma, sum);
    }

    cout << ma << endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int main() {
  int n,m,k;
  cin >> n >> m >> k;
  P a[n];
  for(int i=0; i<n; i++) cin >> a[i].first;
  for(int i=0; i<n; i++) cin >> a[i].second;
  sort(a,a+n,greater<P>());
  int ans=0;
  for(int t=0; t<(1<<n); t++) {
    if(__builtin_popcount(t)>k) continue;
    int sum=0,x=m;
    for(int i=0; i<n; i++) {
      if(!(t&(1<<i))) continue;
      sum+=min(x,a[i].second)*a[i].first;
      x-=min(x,a[i].second);
    }
    ans=max(ans,sum+x);
  }
  cout << ans << endl;
  return 0;
}