Problem: The Patisserie AtCoder sells cakes with number-shaped candles. There are X, Y and Z kinds of cakes with 1-shaped, 2-shaped and 3-shaped candles, respectively. Each cake has an integer value called _deliciousness_ , as follows:    * The deliciousness of the cakes with 1-shaped candles are A_1, A_2, ..., A_X.   * The deliciousness of the cakes with 2-shaped candles are B_1, B_2, ..., B_Y.   * The deliciousness of the cakes with 3-shaped candles are C_1, C_2, ..., C_Z.  Takahashi decides to buy three cakes, one for each of the three shapes of the candles, to celebrate ABC 123.   There are X \times Y \times Z such ways to choose three cakes.   We will arrange these X \times Y \times Z ways in descending order of the sum of the deliciousness of the cakes.   Print the sums of the deliciousness of the cakes for the first, second, ..., K-th ways in this list.

Submission attempts (in order):
/*
g++ main.cpp --std=c++14; ./a.out < input.txt
*/

#include<map>

#include<algorithm>
#include<tuple>

using namespace std;

const auto mod = 1000000007L;

typedef long long ll;

template<typename T>
using V = vector<T>;

template<typename K, typename V>
using M = map<K,V>;

ll sum(tuple<ll,ll,ll> const & t, V<ll> const & A, V<ll> const & B, V<ll> const & C) {
        auto a = get<0>(t);
        auto b = get<1>(t);
        auto c = get<2>(t);
        return A[a]+B[b]+C[c];
}

int main() {
    int X,Y,Z,K;
    cin>>X>>Y>>Z>>K;
    auto A=V<ll>(X);
    for(size_t i = 0; i < X; i++)cin>>A[i];
    sort(A.begin(), A.end(), [](auto a, auto b){return a>b;});
    auto B=V<ll>(Y);
    for(size_t i = 0; i < Y; i++)cin>>B[i];
    sort(B.begin(), B.end(), [](auto a, auto b){return a>b;});
    auto C=V<ll>(Z);
    for(size_t i = 0; i < Z; i++)cin>>C[i];
    sort(C.begin(), C.end(), [](auto a, auto b){return a>b;});
    auto Q=multimap<ll, tuple<ll, ll, ll>, greater<ll>>();
    Q.insert(decltype(Q)::value_type(sum(make_tuple(0,0,0), A, B, C), make_tuple(0,0,0)));
    for(size_t k = 0; k < K; k++)
    {
        auto t = Q.begin();
        cout << t->first << "\n";
        auto a = get<0>(t->second);
        auto b = get<1>(t->second);
        auto c = get<2>(t->second);
        Q.erase(t) ;
        auto d=make_tuple(a, b, c+1);
        if (c+1<X) Q.insert(decltype(Q)::value_type(sum(d, A, B, C), d));
        auto e=make_tuple(a, b+1, c);
        if (c+1<Y) Q.insert(decltype(Q)::value_type(sum(e, A, B, C), e));
        auto f=make_tuple(a+1, b, c);
        if (c+1<Z) Q.insert(decltype(Q)::value_type(sum(f, A, B, C), f));
    }
}

"""
python3 main.py < input.txt
"""
import math
import itertools as it
import heapq

X,Y,Z,K=map(int, input().split())
A=list(sorted(map(int, input().split()), reverse=True))
B=list(sorted(map(int, input().split()), reverse=True))
C=list(sorted(map(int, input().split()), reverse=True))

def evaluate(x,y,z): return (-A[x]-B[y]-C[z], x,y,z)

Q=[]
heapq.heappush(Q, evaluate(0,0,0))
for i in range(1,K+1):
    (e,x,y,z) = heapq.heappop(Q)
    print(-e)
    if x+1 < X and evaluate(x+1, y, z) not in Q:
        heapq.heappush(Q, evaluate(x+1, y, z))
    if y+1 < Y and evaluate(x, y+1, z) not in Q:
        heapq.heappush(Q, evaluate(x, y+1, z))
    if z+1 < Z and evaluate(x, y, z+1) not in Q:
        heapq.heappush(Q, evaluate(x, y, z+1))

Verdicts: Runtime Error

Accepted