1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
const LL INF = 1000000000000000000ll;

struct S {
  LL v;
  char o;

  bool operator<(const S& b) const {
    return v < b.v;
  }
};

template <typename X>
void mmin(X& a, const X& b) {
  if (b < a) a = b;
}

vector<char> solve(LL l, int n, int k, vector<int> a, vector<int> b) {
  vector<vector<S>> t;
  t.push_back(vector<S>({S{0ll, 'x'}}));
  for (int i=0; i<n; ++i) {
    t.push_back(vector<S>(i+2, S{INF, '-'}));
    for (int j=0; j<=i; ++j) {
      if (t[i][j].o != '-') {
        mmin(t[i+1][j+1], S{max(t[i][j].v, 0ll) + a[i], 'A'});
        mmin(t[i+1][j], S{max(t[i][j].v, 0ll) + b[i], 'B'});
      }
    }

    for (int j=0; j<=i+1; ++j) {
      if (t[i+1][j].v >= l) {
        t[i+1][j].o = '-';
      }
//      printf("%c", t[i+1][j].o);
    }
//    printf("\n");
  }

  if (t[n][k].o == '-') return {};

  vector<char> res;
  while (n > 0) {
    res.push_back(t[n][k].o);
    --n;
    if (res.back() == 'A') {
     --k; 
    } else if (res.back() == 'B') {
    } else {
      printf("ERROR\n");
    }
  }
  reverse(res.begin(), res.end());
  return res;
}

int main() {
  int n, k; scanf("%d %d", &n, &k);
  vector<int> a(n), b(n);
  for (int i=0; i<n; ++i) scanf("%d", &a[i]);
  for (int i=0; i<n; ++i) scanf("%d", &b[i]);

  LL A = 0, B = INF, C;
  vector<char> best;
  while (B-A > 1) {
    C = (A+B) / 2;
//    printf("Limit: %lld\n", C);
    vector<char> sol = solve(C, n, k, a, b);
    if (!sol.empty()) {
      swap(best, sol);
      B = C;
    } else {
      A = C;
    }
  }
  printf("%lld\n", B-1);
  for (int i=0; i<n; ++i) printf("%c", best[i]);
  printf("\n");
  return 0;
}