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: // package c1618;
  
  import java.io.File;
  import java.lang.invoke.MethodHandles;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.Random;
  import java.util.Scanner;
  import java.util.TreeMap;
  
  //
  // Codeforces Round #760 (Div. 3) 2021-12-14 06:35
  // G. Trader Problem
  // https://codeforces.com/contest/1618/problem/G
  // time limit per test 4.5 seconds; memory limit per test 512 megabytes
  // public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
  //
  // 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 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
  */
  //
  public class C1618G {
    static final int MOD = (int)1e9+7;
    static final Random RAND = new Random();
  
    static class TestCase {
      int n;
      int m;
      int q;
      int[] a;
      int[] b;
      int[] c;
  
      // combined and sorted with flag indicate whether belongs to a or b
      int[][] arr;
  
      // presum[i] is the sum of numbers in arr index range [0,i)
      long[] presum;
  
      // cta[i] is the number of a values in arr index range [0,i)
      int[] cta;
  
      static long[] solve(int[] a, int[] b, int[] c) {
        TestCase tc = new TestCase(a, b, c);
        return tc.solve();
      }
  
      public TestCase(int[] a, int[] b, int[] c) {
        this.n = a.length;
        this.m = b.length;
        this.q = c.length;
        this.a = a;
        this.b = b;
        this.c = c;
        this.arr = combineSort(a, b);
        this.presum = new long[n+m+1];
        this.cta = new int[n+m+1];
        for (int i = 0; i < n + m; i++) {
          presum[i+1] += presum[i] + arr[i][0];
          cta[i+1] = cta[i] + (arr[i][1] == 0 ? 1 : 0);
        }
      }
  
      long[] solve() {
        // Map from gap (to next chunk) to list of chunk
        TreeMap<Integer, List<Chunk>> gaps = getGapToChunksMap(arr);
  
        // sorted query by k value and with index
        int[][] ca = sortWithIndex(c);
  
        long suma = 0;
        for (int v : a) {
          suma += v;
        }
  
        long[] ans = new long[q];
        int prev = 0;
        for (int i = 0; i < q; i++) {
          int k = ca[i][0];
          int idx = ca[i][1];
          if (k != prev) {
            // System.out.format("  k:%d gaps:\n%s", k, trace(gaps));
            Iterator<Map.Entry<Integer, List<Chunk>>> it = gaps.entrySet().iterator();
            while (it.hasNext()) {
              Map.Entry<Integer, List<Chunk>> e = it.next();
              if (e.getKey() > k) {
                break;
              }
              for (Chunk chunk : e.getValue()) {
                // merge chunk into next if exists
                suma += mergeChunk(chunk, cta, presum);
              }
              it.remove();
            }
          }
          prev = k;
          ans[idx] = suma;
        }
        return ans;
      }
  
      long[] solveNaive() {
        int[][] ar = combineSort(a, b);
  
        // sorted query by k value and with index
        int[][] ca = sortWithIndex(c);
        long suma = 0;
        for (int v : a) {
          suma += v;
        }
        int n = a.length;
        int m = b.length;
        int q = c.length;
        long[] ans = new long[q];
        for (int i = 0; i < q; i++) {
          int k = ca[i][0];
          int idx = ca[i][1];
          // System.out.format("  k:%d idx:%d\n", k, idx);
          boolean changed = true;
          while (changed) {
            changed = false;
            for (int j = n + m - 2; j >= 0; j--) {
              if (ar[j][1] == 0 && ar[j+1][1] == 1 && ar[j][0] + k >= ar[j+1][0]) {
                changed = true;
                // System.out.format("    changed j:%d %d %d\n", j, arr[j][0], arr[j+1][0]);
                suma += ar[j+1][0] - ar[j][0];
                ar[j+1][1] = 0;
                ar[j][1] = 1;
  
              }
            }
          }
          ans[idx] = suma;
        }
        return ans;
      }
  
      // Map from gap (to next chunk) to list of chunk
      //   idx:   0   1   2   3   4   5   6   7   8
      // value:   1   1   3   4   7   7   8   9
      //   gap:   ______2___1___3_______1___1___oo
      static TreeMap<Integer, List<Chunk>> getGapToChunksMap(int[][] arr) {
        int len = arr.length;
        TreeMap<Integer, List<Chunk>> gaps = new TreeMap<>();
        int ib = 0;
        Chunk pc = null;
        while (ib < len) {
          int ie = ib;
          while (ie + 1 < len && arr[ie + 1][0] == arr[ib][0]) {
            ie++;
          }
          Chunk chunk = new Chunk(ib, ie, pc);
          if (pc != null) {
            pc.next = chunk;
          }
          pc = chunk;
          if (ie == len -1) {
            break;
          }
  
          int gap = arr[ie+1][0] - arr[ie][0];
          gaps.computeIfAbsent(gap, x -> new ArrayList<>()).add(chunk);
          // System.out.format("  chunk %s gap:%d\n", chunk, gap);
          ib = ie + 1;
        }
        return gaps;
      }
  
      static class Chunk {
        // begin and end index, inclusive
        int ib;
        int ie;
        Chunk prev;
        Chunk next;
  
        public Chunk(int ib, int ie, Chunk prev) {
          this.ib = ib;
          this.ie = ie;
          this.prev = prev;
        }
  
        @Override
        public
        String toString() {
          return String.format("[%2d,%2d]", ib, ie);
        }
      }
  
      // Array of [value, 0 for a or 1 for b]
      static int[][] combineSort(int[] a, int[] b) {
        int n = a.length;
        int m = b.length;
        int[][] arr = new int[n+m][2];
        for (int i = 0; i < n; i++) {
          arr[i][0] = a[i];
          arr[i][1] = 0;
        }
        for (int i = 0; i < m; i++) {
          arr[i + n][0] = b[i];
          arr[i + n][1] = 1;
        }
        Arrays.sort(arr, (x,y)->x[0] - y[0]);
        return arr;
      }
  
      static int[][] sortWithIndex(int[] c) {
        int q = c.length;
        int[][] ca = new int[q][2];
        for (int i = 0; i < q; i++) {
          ca[i][0] = c[i];
          ca[i][1] = i;
        }
        Arrays.sort(ca, (x,y)->x[0] - y[0]);
        return ca;
      }
  
      // merge chunk with its next one
      static long mergeChunk(Chunk chunk, int[] cta, long[] presum) {
        Chunk next = chunk.next;
        if (next == null) {
          return 0;
        }
        int nb = next.ib;
        // number of elements in a in current and next chunk
        int nac = cta[chunk.ie + 1] - cta[chunk.ib];
        int nan = cta[next.ie + 1] - cta[next.ib];
        // System.out.format("  k:%d %s %s nac:%d nan:%d\n", k, chunk, next, nac, nan);
        // current and next chunk sum
        long sumc = presum[chunk.ie + 1] - presum[chunk.ie + 1 - nac];
        long sumn = presum[next.ie + 1] - presum[next.ie + 1 - nan];
        next.ib = chunk.ib;
        long sum = presum[next.ie + 1] - presum[next.ie + 1 - nac - nan];
        // Properly remove current chunk from linked list.
        if (chunk.prev != null) {
          chunk.prev.next = next;
          next.prev = chunk.prev;
        }
        // System.out.format("      merged %s [%2d,%2d] into %s %d+%d->%d suma:%d\n",
        //    chunk, nb, next.ie, next, sumc, sumn, sum, suma);
        return sum - sumc - sumn;
      }
  
      static String trace(TreeMap<Integer, List<Chunk>> gaps) {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Integer, List<Chunk>> e : gaps.entrySet()) {
          sb.append(String.format("   %2d: ", e.getKey()));
          for (Chunk chunk : e.getValue()) {
            sb.append(chunk);
          }
          sb.append("\n");
        }
        return sb.toString();
      }
    }
  
    static void doTest(int[] a, int[] b, int[] c) {
      int q = c.length;
      System.out.println(Arrays.toString(a));
      System.out.println(Arrays.toString(b));
      System.out.println(Arrays.toString(c));
      TestCase tc = new TestCase(a, b, c);
      long[] ans = tc.solve();
      long[] exp = tc.solveNaive();
      for (int i = 0; i < q; i++) {
        System.out.format("%d %s\n", ans[i], exp[i] == ans[i] ? "" : " Expected " + exp[i]);
      }
    }
  
    static void doTest() {
      int n = 100;
      int m = 50;
      int q = 50;
      int[] a = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = 1 + RAND.nextInt(1000);
      }
      int[] b = new int[m];
      for (int i = 0; i < m; i++) {
        b[i] = 1 + RAND.nextInt(1000);
      }
      int[] c = new int[q];
      for (int i = 0; i < q; i++) {
        c[i] = RAND.nextInt(40);
      }
      doTest(a, b, c);
      System.exit(0);
    }
  
    public static void main(String[] args) {
      // doTest();
      Scanner in = getInputScanner();
      int n = in.nextInt();
      int m = in.nextInt();
      int q = in.nextInt();
      int[] a = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = in.nextInt();
      }
      int[] b = new int[m];
      for (int i = 0; i < m; i++) {
        b[i] = in.nextInt();
      }
      int[] c = new int[q];
      for (int i = 0; i < q; i++) {
        c[i] = in.nextInt();
      }
      long[] ans = TestCase.solve(a, b, c);
      StringBuilder sb = new StringBuilder();
      for (long v : ans) {
        sb.append(v);
        sb.append("\n");
      }
      System.out.print(sb);
      in.close();
    }
  
    static Scanner getInputScanner() {
      try {
        final String USERDIR = System.getProperty("user.dir");
        final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
        final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
        return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
      } catch (Exception e) {
        return new Scanner(System.in);
      }
    }
  }
  