description: Monocarp plays a computer game (yet again!). This game has a unique trading mechanics.
  
  To trade with a character, Monocarp has to choose one of the items he possesses and trade it for some item the other character possesses. Each item has an integer price. If Monocarp's chosen item has price x, then he can trade it for any item (exactly one item) with price not greater than x+k.
  
  Monocarp initially has n items, the price of the i-th item he has is a_i. The character Monocarp is trading with has m items, the price of the i-th item they have is b_i. Monocarp can trade with this character as many times as he wants (possibly even zero times), each time exchanging one of his items with one of the other character's items according to the aforementioned constraints. Note that if Monocarp gets some item during an exchange, he can trade it for another item (since now the item belongs to him), and vice versa: if Monocarp trades one of his items for another item, he can get his item back by trading something for it.
  
  You have to answer q queries. Each query consists of one integer, which is the value of k, and asks you to calculate the maximum possible total cost of items Monocarp can have after some sequence of trades, assuming that he can trade an item of cost x for an item of cost not greater than x+k during each trade. Note that the queries are independent: the trades do not actually occur, Monocarp only wants to calculate the maximum total cost he can get.
  
  Input
  
  The first line contains three integers n, m and q (1 ≤ n, m, q ≤ 2 ⋅ 10^5).
  
  The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the prices of the items Monocarp has.
  
  The third line contains m integers b_1, b_2, ..., b_m (1 ≤ b_i ≤ 10^9) — the prices of the items the other character has.
  
  The fourth line contains q integers, where the i-th integer is the value of k for the i-th query (0 ≤ k ≤ 10^9).
  
  Output
  
  For each query, print one integer — the maximum possible total cost of items Monocarp can have after some sequence of trades, given the value of k from the query.
  
  Example
  
  Input
  
  
  3 4 5
  10 30 15
  12 31 14 18
  0 1 2 3 4
  
  
  Output
  
  
  55
  56
  60
  64
  64
solution: import java.io.*;
  import java.util.*;
  
  public class Main {
  
      static void sortArray(int[] a) {
          Random random = new Random();
  
          for (int i = 0; i < a.length; i++) {
              int randomPos = random.nextInt(a.length);
              int t = a[i];
              a[i] = a[randomPos];
              a[randomPos] = t;
          }
          Arrays.sort(a);
      }
  
      private static class Vertex implements Comparable<Vertex> {
          private int value;
          private boolean initial;
          private int index;
          private int set;
  
          public Vertex(int value, boolean initial) {
              this.value = value;
              this.initial = initial;
          }
  
          @Override
          public int compareTo(Vertex o) {
              return Integer.compare(value, o.value);
          }
      }
  
      private static class Edge implements Comparable<Edge> {
          private Vertex u;
          private Vertex v;
          private int value;
  
          public Edge(Vertex u, Vertex v, int value) {
              this.u = u;
              this.v = v;
              this.value = value;
          }
  
          @Override
          public int compareTo(Edge o) {
              return Integer.compare(value, o.value);
          }
      }
  
      private static class VerticesSet {
          Set<Vertex> vertices = new HashSet<>();
          int initialVertices = 0;
          int maxIndex = -1;
          long deltaAns = 0;
  
          private VerticesSet(Vertex vertex) {
              vertices.add(vertex);
              initialVertices = vertex.initial ? 1 : 0;
              maxIndex = vertex.index;
              deltaAns = vertex.initial ? vertex.value : 0;
          }
  
      }
  
      public static void main(String[] args) throws FileNotFoundException {
          InputReader in = new InputReader(System.in);
          PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  
          int n = in.nextInt();
          int m = in.nextInt();
          int q = in.nextInt();
  
          Vertex[] a = readVertices(in, n, true, 0);
          Vertex[] b = readVertices(in, m, false, n);
  
          int[][] queries = new int[q][2];
          for (int i = 0; i < q; i++) {
              queries[i] = new int[]{in.nextInt(), i};
          }
  
          List<Edge> edges = new ArrayList<>();
          for (int i = 0; i < m - 1; i++) {
              edges.add(new Edge(b[i], b[i + 1], b[i + 1].value - b[i].value));
          }
  
          long[] aPrefSums = new long[n + 1];
          for (int i = 1; i <= n; i++) {
              aPrefSums[i] = aPrefSums[i - 1] + a[i - 1].value;
          }
  
          Vertex[] ab = new Vertex[n + m];
          System.arraycopy(a, 0, ab, 0, n);
          System.arraycopy(b, 0, ab, n, m);
          Arrays.sort(ab);
          long[] abPrefSums = new long[n + m + 1];
          for (int i = 1; i <= n + m; i++) {
              abPrefSums[i] = abPrefSums[i - 1] + ab[i - 1].value;
          }
  
          int t = 0;
          for (int i = 0; i < n; i++) {
              if (i < n - 1) {
                  edges.add(new Edge(a[i], a[i + 1], a[i + 1].value - a[i].value));
              }
              while (t < m && b[t].value <= a[i].value) {
                  t++;
              }
              if (t < m) {
                  edges.add(new Edge(a[i], b[t], b[t].value - a[i].value));
              }
              if (t > 0) {
                  edges.add(new Edge(a[i], b[t - 1], -b[t - 1].value + a[i].value));
              }
          }
          Collections.sort(edges);
  
          Arrays.sort(queries, Comparator.comparingInt(o -> o[0]));
  
          long[] ans = new long[q];
          int currentEdge = 0;
  
          long currentAns = 0;
          for (int i = 0; i < n; i++) {
              currentAns += a[i].value;
          }
  
          VerticesSet[] sets = new VerticesSet[n + m];
          for (int i = 0; i < n + m; i++) {
              ab[i].set = i;
              ab[i].index = i;
              sets[i] = new VerticesSet(ab[i]);
          }
  
          for (int i = 0; i < q; i++) {
              int k = queries[i][0];
              while (currentEdge < edges.size() && edges.get(currentEdge).value <= k) {
                  Edge edge = edges.get(currentEdge);
  
                  if (edge.u.set != edge.v.set) {
                      Vertex u, v;
                      if (sets[edge.u.set].vertices.size() < sets[edge.v.set].vertices.size()) {
                          u = edge.u;
                          v = edge.v;
                      } else {
                          u = edge.v;
                          v = edge.u;
                      }
  
                      sets[v.set].initialVertices += sets[u.set].initialVertices;
                      sets[v.set].maxIndex = Math.max(sets[u.set].maxIndex, sets[v.set].maxIndex);
                      sets[v.set].deltaAns += sets[u.set].deltaAns;
  
                      for (Vertex w : sets[u.set].vertices) {
                          sets[v.set].vertices.add(w);
                          w.set = v.set;
                      }
  
                      if (sets[v.set].initialVertices > 0) {
                          int r = sets[v.set].maxIndex + 1;
                          int l = Math.max(0, r - sets[v.set].initialVertices);
                          long newDelta = abPrefSums[r] - abPrefSums[l];
                          currentAns -= sets[v.set].deltaAns;
                          currentAns += newDelta;
                          sets[v.set].deltaAns = newDelta;
                      }
  
                  }
  
                  currentEdge++;
              }
              ans[queries[i][1]] = currentAns;
          }
  
          for (int i = 0; i < q; i++) {
              out.println(ans[i]);
          }
  
          out.close();
      }
  
      private static Vertex[] readVertices(InputReader in, int n, boolean initial, int initialSet) {
          Vertex[] a = new Vertex[n];
          for (int i = 0; i < n; i++) {
              a[i] = new Vertex(in.nextInt(), initial);
          }
          Arrays.sort(a);
          return a;
      }
  
      private static void outputArray(List<Integer> ans, PrintWriter out, boolean addOne) {
          StringBuilder str = new StringBuilder();
          for (long an : ans) {
              str.append(addOne ? (an + 1) : an).append(" ");
          }
          out.println(str);
  //        out.flush();
      }
  
      private static class InputReader {
          public BufferedReader reader;
          public StringTokenizer tokenizer;
  
          public InputReader(InputStream stream) {
              reader = new BufferedReader(new InputStreamReader(stream), 32768);
              tokenizer = null;
          }
  
          private String next() {
              while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                  try {
                      tokenizer = new StringTokenizer(reader.readLine());
                  } catch (IOException e) {
                      throw new RuntimeException(e);
                  }
              }
              return tokenizer.nextToken();
          }
  
          public String nextString() {
              try {
                  return reader.readLine();
              } catch (IOException e) {
                  throw new RuntimeException(e);
              }
          }
  
          public int nextInt() {
              return Integer.parseInt(next());
          }
  
          public long nextLong() {
              return Long.parseLong(next());
          }
  
          public double nextDouble() {
              return Double.parseDouble(next());
          }
  
          public char nextChar() {
              return next().charAt(0);
          }
  
          public String nextWord() {
              return next();
          }
  
          private List<Integer>[] readTree(int n) {
              return readGraph(n, n - 1);
          }
  
          private List<Integer>[] readGraph(int n, int m) {
              List<Integer>[] result = new List[n];
              for (int i = 0; i < n; i++) {
                  result[i] = new ArrayList<>();
              }
              for (int i = 0; i < m; i++) {
                  int u = nextInt() - 1;
                  int v = nextInt() - 1;
                  result[u].add(v);
                  result[v].add(u);
              }
              return result;
          }
  
          private Map<Integer, Long>[] readWeightedGraph(int n, int m) {
              Map<Integer, Long>[] result = new HashMap[n];
              for (int i = 0; i < n; i++) {
                  result[i] = new HashMap<>();
              }
              for (int i = 0; i < m; i++) {
                  int u = nextInt() - 1;
                  int v = nextInt() - 1;
                  long w = nextLong();
                  result[u].put(v, Math.min(w, result[u].getOrDefault(v, Long.MAX_VALUE)));
                  result[v].put(u, Math.min(w, result[v].getOrDefault(u, Long.MAX_VALUE)));
              }
              return result;
          }
  
          private int[] readArray(int size, boolean subOne) {
              int[] a = new int[size];
              for (int i = 0; i < size; i++) {
                  a[i] = nextInt() + (subOne ? -1 : 0);
              }
              return a;
          }
  
          private long[] readLongArray(int size) {
              long[] a = new long[size];
              for (int i = 0; i < size; i++) {
                  a[i] = nextLong();
              }
              return a;
          }
      }
  }