:- use_module(library(clpfd)).


main :-
    read_num(N),
    read_num(M),
    read_num(K),
    read_n_num_list(N, A),
    read_n_num_list(M, B),

    total_times(A, TotalA),
    total_times(B, TotalB),

    find_answer(N, M, K, TotalA, TotalB),
    halt.


find_answer(N, M, K, TotalA, TotalB) :-

        X in 0 .. N,
        find_max_y(N, TotalA, K, TotalB, MaxY),
        Y in 0 .. MaxY,

        chain(TotalA, #<),
        chain(TotalB, #<),
        
        element(X, TotalA, TimeA),
        element(Y, TotalB, TimeB),
        
        0 #=< TimeA, TimeA #=< K,
        0 #=< TimeB, TimeB #=< K,
        TimeA + TimeB #=< K,

        labeling([down, max(X + Y)], [X, Y]),

        Ans is X + Y,

        write(Ans),
        nl.
find_answer(_, _, _, _, _) :-
        write(0),
        nl.

find_max_y(N, TotalA, K, TotalB, MaxY) :-
        nth1(N, TotalA, MaxTotalTimeA),
        Rest is K - MaxTotalTimeA,
        reverse(TotalB, ReversedTotalB),
        find_near_time_b(ReversedTotalB, Rest, NearTimeB),
        nth1(MaxY, TotalB, NearTimeB).

find_near_time_b([], Time, 0).
find_near_time_b([H|T], Time, H) :-
        H =< Time.
find_near_time_b([H|T], Time, X) :-
        H > Time,
        find_near_time_b(T, Time, X).

total_times(L, Total) :-
        total_times(L, [0], Total).
total_times([], Acc, Total) :-
        reverse(Acc, Reversed),
        select(0, Reversed, Total).
total_times([H|T], [AccH|AccT], Total) :-
        NewAcc is AccH + H,
        total_times(T, [NewAcc, AccH|AccT], Total).


read_n_num_list(Num, List) :-
    read_n_num_list_aux(Num, [], List),
    !.
read_n_num_list_aux(0, List, List).
read_n_num_list_aux(Num, Old, Accum) :-
    read_num(NewItem),
    NewNum is Num - 1,
    append(Old, [NewItem], NewList),
    read_n_num_list_aux(NewNum, NewList, Accum).


read_str(S) :-
        read_string(current_input, ' \n', '', _, S).
 
read_num(N) :-
	read_str(S),
	number_string(N, S).


:- main.
