(import '(java.util HashSet PriorityQueue))
(require '[clojure.pprint :refer [pprint]])
(defrecord StateABC123D
  [candidates
   best-score
   bfs-visited      ; vertex = [Ia, Ib, Ic] where Ix := I-th candidates for series x
   bfs-edge-candidates ; priority queue over {:penalty ?? :from v1 :to v2} [v1 v2]s, weighted on :penalty
   emitter])
(defrecord AbsolutePriorityQueue [queue comp picker])
(defn make-absolute-priority-queue [comp picker]
  (->AbsolutePriorityQueue (PriorityQueue. comp) comp picker))
(defn enqueue [apq elem] (-> apq :queue (.add elem)))
(defn singleton? [coll] (and (seq coll) (empty? (rest coll))))
(defn dequeue [apq]
  (let [{pq :queue :keys [picker comp]} apq
        less? (fn [a b] (< (comp a b) 0))
        cands (loop [pivot (.poll pq)
                     acc [pivot]]
                (cond (or (.isEmpty pq) (less? pivot (.peek pq))) acc
                      :else (recur pivot (conj acc (.poll pq)))))]
    (cond (singleton? cands) (first cands)
          :else (let [[picked r] (picker cands)]
                  (.addAll pq r)
                  picked))))
(defn sort-desc [coll] (sort (comparator >) coll))
(defn vertex-value [state [Ia Ib Ic]]
  (let [candidates (or (:candidates state) state)
        F (fn [state series index] (-> candidates series (nth index)))]
    (if (or (>= Ia (count (:A candidates)))
            (>= Ib (count (:B candidates)))
            (>= Ic (count (:C candidates))))
      nil
      (+ (F state :A Ia) (F state :B Ib) (F state :C Ic)))))
(defn lexico-compare [coll1 coll2]
  (loop [[v1 & r1 :as c1] coll1
         [v2 & r2 :as c2] coll2]
    (cond (or (empty? c1) (empty? c2)) 0
          (< v1 v2) -1
          (> v1 v2) 1
          :else (recur r1 r2))))
(let [F :penalty]
  (defn edge-comp [e1 e2]
    (lexico-compare (F e1) (F e2))))
(defn enrich [visited best-score candidates edge]
  #_(println "enriching" edge)
  (let [{:keys [to penalty ep]
         :or {ep []}} (:enriched edge)
        stretch (reduce (partial mapv +) to ep)
        cands (for [[s k tr] [[:A 0 [1 0 0]] [:B 1 [0 1 0]] [:C 2 [0 0 1]]]
                    :let [pong (mapv + stretch tr)
                          val (vertex-value candidates pong)]
                    :when (and val (not (.contains visited pong)))]
                {:ep (conj ep tr) :sub-penalty (- best-score val)})
        cand (cond (empty? cands) nil
                   (singleton? cands) (first cands)
                   :else (apply min-key :sub-penalty cands))]
    (if cand
      (update edge :enriched
        #(assoc % :ep (:ep cand) :penalty (conj penalty (:sub-penalty cand))))
      edge)))
(defn pick-edges [visited best-score candidates cands]
  (let [tos (set (map :to cands))
        cands (map #(first (filter (fn [cand] (= % (:to cand))) cands)) tos)]
    (if (singleton? cands)
      [(first cands) []]
      (loop [[a b :as cands] (map (fn [x] {:enriched x :original x}) cands)]
       (if (< (edge-comp (:enriched a) (:enriched b)) 0)
         [(:original a) (map :original (rest cands))]
         (let [enriched (->> cands
                          (filter #(= (get-in a [:enriched :penalty])
                                      (get-in % [:enriched :penalty])))
                          (map (partial enrich visited best-score candidates)))]
           (if (= cands enriched) [(:original (first cands)) (map :original (rest cands))]
                                  (recur (sort-by :enriched edge-comp enriched)))))))))
(defn init-state [emitter as bs cs]
  (let [as (sort-desc as)
        bs (sort-desc bs)
        cs (sort-desc cs)
        candidates {:A (vec (sort-desc as))
                    :B (vec (sort-desc bs))
                    :C (vec (sort-desc cs))}
        bfs-visited (HashSet.)
        best-score (vertex-value candidates [0 0 0])]
    (->StateABC123D
      candidates
      best-score
      bfs-visited
      (make-absolute-priority-queue
        edge-comp
        (partial pick-edges bfs-visited best-score candidates))
      emitter)))
(defn dump-state [state]
  (-> state
    (update :bfs-edge-candidates
      (fn [q] (vec (PriorityQueue. (:queue q)))))
    (pprint)))
(defn visit-vertex [state vertex]
  (let [{visited :bfs-visited
         edges :bfs-edge-candidates
         :keys [emitter best-score]} state
        [Ia Ib Ic] vertex]
    (emitter state vertex)
    (.add visited vertex)
    (doseq [[series k] [[:A 0] [:B 1] [:C 2]]]
      (when (< (inc (nth vertex k)) (count (-> state :candidates series)))
        (enqueue edges {:from    vertex :to (update vertex k inc)
                        :penalty [(- best-score (vertex-value state (update vertex k inc)))]})))))
(defn emit-next [state]
  (let [{edges :bfs-edge-candidates
         visited :bfs-visited} state
        next (->> (repeatedly #(dequeue edges))
               (filter #(not (.contains visited (:to %))))
               first :to)]
    (visit-vertex state next)))
(defn abc123-D [as bs cs K]
  (let [collector (transient [])
        emitter (fn [state v] (conj! collector (vertex-value state v)))
        state (init-state emitter as bs cs)]
    #_(dump-state state)
    (visit-vertex state [0 0 0])
    (dotimes [n (dec K)] (emit-next state))
    (persistent! collector)))
(defn main-abc123-D []
  (let [X (read) Y (read) Z (read) K (read)
        as (doall (for [_ (range X)] (read)))
        bs (doall (for [_ (range Y)] (read)))
        cs (doall (for [_ (range Z)] (read)))]
    (run! println (abc123-D as bs cs K))))
(main-abc123-D)