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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC target("sse,sse2,sse3,mmx,abm,tune=native") // for szkopul and sio only
typedef long long lld;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define For(i,s,a) for(lld i = (lld)s; i < (lld)a; ++i)
#define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it)
#define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it)
#define pb push_back
#define eb emplace_back
#define ff first
#define dd second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define make_unique(x) (x).erase( unique(all(x)), (x).end())
#define popcnt(x) __builtin_popcount(x)
#define sz size()
#define time_since duration_cast< milliseconds >(system_clock::now().time_since_epoch())
 
template<typename Ta, typename Tb>
ostream & operator <<(ostream & os, pair<Ta, Tb> x){
	return os << x.ff << " " << x.dd;
}

const int N = 1e5 + 1;
const int smallN = 7e3 + 1;

vector<vector<lld>>dp;
lld c[N], d[N];
char ans[N];

#define fmax(a, b) ((a) > (b) ? (a) : (b))
#define fmin(a, b) ((a) < (b) ? (a) : (b))
const lld inf = 0x3f3f3f3f3f3f3f3fll;

bool ok(lld x, int n, int k) {
	For(i, 0, n)
	For(j, 0, k + 1)
		dp[i][j] = inf;
	dp[0][0] = 0;
	For(i, 1, n + 1)
	For(j, 0, fmin(i, k) + 1) {
		dp[i][j] = fmax(0, dp[i - 1][j]) + d[i - 1];
		if(j)
			dp[i][j] = fmin(dp[i][j], fmax(0, dp[i - 1][j - 1]) + c[i - 1]);
		if(dp[i][j] > x)
			dp[i][j] = inf;
	}
	return dp[n][k] < inf;
}

void write(int n, int k) {
	while(n) {
		if(dp[n][k] == fmax(0, dp[n - 1][k]) + d[n - 1]) {
			ans[n - 1] = 'B';
			--n;
		} else {
			ans[n - 1] = 'A';
			--n;
			--k;
		}
	}
	if(k)
		exit(69);
}

void solve(void) {
	int n, t;
	scanf("%d%d", &n, &t);
	dp = vector<vector<lld>>(n + 1, vector<lld>(t + 1));
	For(i, 0, n)
		scanf("%lld", &c[i]);
	For(i, 0, n)
		scanf("%lld", &d[i]);
	lld p = 0, k = 1e14, mid = 0;
	while(p <= k) {
		mid = (p + k) >> 1ll;
		//cout << p << " " << k << " " << mid << endl;
		if(ok(mid, n, t)) 
			k = mid - 1;
		else 
			p = ++mid;
	}
	ok(mid, n, t);
	printf("%lld\n", mid);
	write(n, t);
	printf("%s\n", ans);
}

int32_t main(void){
	int t = 1;
	//scanf("%d", &t);
	while(t--)
		solve();
}