Problem: E: Red Black Balloons

Story

Homura-chan's dream comes true. It means ICPC Asia regional contest 20xx will be held in Sapporo! Homura-chan has been working hard for the preparation. And finally, it's the previous day of the contest. Homura-chan started to stock balloons to be delivered to contestants who get accepted. However, she noticed that there were only two colors of balloons: red and black.

Problem Statement

ICPC Asia regional contest in Sapporo plans to provide N problems to contestants. Homura-chan is a professional of contest preparation, so she already knows how many contestants would get acceptance for each problem (!!), a_i contestants for the i-th problem. You can assume the prediction is perfectly accurate. Ideally, Homura-chan would assign a distinct color of a balloon to each problem respectively. But you know, she has only two colors red and black now. Thus, Homura-chan comes up with the idea to differentiate the size of balloons in K levels, that is, each problem has a balloon with a distinct pair of (color, size).

Homura-chan now has r_i red balloons with size i (1 \leq i \leq K) and b_j black balloons with size j (1 \leq j \leq K). Suppose we assign a pair (c_i, s_i) of a color c_i (red or black) and a size s_i to the i-th problem, for each i. As noted, we have to assign distinct pairs to each problem, more precisely, (c_i, s_i) \neq (c_j, s_j) holds for i \neq j. Moreover, the number of balloons with (c_i, s_i) must be no less than a_i. In the case that there are no such assignments, Homura-chan can change the size of balloons by her magic power. Note that Homura-chan doesn't know magic to change the color of balloons, so it's impossible.

Your task is to write a program computing the minimum number of balloons whose size is changed by Homura-chan's magic to realize an assignment satisfying the above-mentioned conditions. If there is no way to achieve such an assignment even if Homura-chan changes the size of balloons infinitely, output `-1` instead.

Input


N K
a_1 ... a_N
r_1 ... r_K
b_1 ... b_K


Constraints

* 1 \leq N,K \leq 60
* N \leq 2K
* 1 \leq a_i \leq 50 (1 \leq i \leq N)
* 1 \leq r_j,b_j \leq 50 (1 \leq j \leq K)
* Inputs consist only of integers.



Output

Output the minimum number of balloons whose size is changed to achieve an assignment in a line. If there are no ways to achieve assignments, output `-1` instead.

Sample Input 1


3 2
6 5 4
8 1
7 1


Output for Sample Input 1


3

Homura-chan changes the size of three red balloons from 1 to 2. Then she can assign (black,1) to the problem 1, (red,1) to the problem 2, and (red,2) to the problem 3.

Sample Input 2


2 1
50 50
2
3


Output for Sample Input 2


-1

Sample Input 3


4 3
3 10 28 43
40 18 2
26 7 11


Output for Sample Input 3


5





Example

Input

3 2
6 5 4
8 1
7 1


Output

3

Solution (in CPP):

Solution:
/// u ? wara

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define X first
#define Y second

#define all(v) (v).begin(), (v).end()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,b) FOR(i,0,b)
#define reps FOR
#define eb emplace_back
#define pb eb

template<class T> inline bool MX(T &l, const T &r) { return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l, const T &r) { return l>r?l=r,1:0;}

using LL = long long;
using pii = pair<int, int>;
using pll = pair<LL, LL>;

const int INF = 0x3fffffff;
const int B = 3145;

int N;
int K;
int a[70];
int r[70];
int b[70];
int dp[70][70][B];

signed main() {
  int asum = 0;
  int bsum = 0;
  int rsum = 0;
  cin >> N >> K;
  reps(i, 1, N+1) {
    cin >> a[i];
    asum += a[i];
  }
  sort(a+1, a+N+1, greater<int>());
  reps(i, 1, K+1) {
    cin >> r[i];
    rsum += r[i];
  }
  sort(r+1, r+K+1, greater<int>());
  reps(i, 1, K+1) {
    cin >> b[i];
    bsum += b[i];
  }
  sort(b+1, b+K+1, greater<int>());

  fill(dp[0][0], dp[N+1][0], INF);
  dp[0][0][0] = 0;
  rep(i, N) {
    int lim = min(i, K);
    rep(j, lim+1) {
      int k = i - j;
      if (k > K) continue;
      assert(k >= 0 && k <= K);
      rep(l, B) {
        int cost = dp[i][j][l];
        if (cost == INF) continue;
        //cout << i << ", " << j << ", " << l << endl;
        // ai+1 rj+1
        if (j < K && l+a[i+1] < B) {
          int d = r[j+1] - a[i+1];
          int nl = l+a[i+1];
          //cout <<"upd"<< i+1 << ", " << j+1 << ", " << nl << endl;
          if (d >= 0) {
            MN(dp[i+1][j+1][nl], cost);
          } else {
            MN(dp[i+1][j+1][nl], cost + abs(d));
          }
        }

        if (k < K) {
          int d = b[k+1] - a[i+1];
          //cout <<"upd"<< i+1 << ", " << j << ", " << l << endl;
          if (d >= 0) {
            MN(dp[i+1][j][l], cost);
          } else {
            MN(dp[i+1][j][l], cost + abs(d));
          }
        }
      }
    }
  }

  int ans = INF;
  rep(j, K+1) {
    int k = N - j;
    if (k > K) continue;
    if (k < 0) continue;
    rep(l, B) {
      assert(k >= 0 && k <= K);
      int rsup = rsum - l;
      int bsup = bsum - (asum - l);
      if (rsup < 0 || bsup < 0) continue;
      MN(ans, dp[N][j][l]);
    }
  }
  if (ans == INF) cout << "-1" << endl;
  else cout << ans << endl;
}