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
#include <bits/stdc++.h>
using namespace std;
void imax(int &a, int b){
	a=max(a, b);
}
void imin(int &a, int b){
	a=min(a, b);
}
void lmax(long long &a, long long b){
	a=max(a, b);
}
void lmin(long long &a, long long b){
	a=min(a, b);
}
/*
	WARNING: I'm using strange bracket style!
*/
const long long INF=(1ll<<60);
const int SIZEB=1000000;
const int SIZE=4000;
long long DP[SIZE][SIZE];
int from[SIZE][SIZE];
int a[SIZE], b[SIZE];
string ans;
int n, k;
bool check(long long x, bool gen=false){
	for (int i=0; i<=n+10; i++)
		for (int j=0; j<=n+10; j++)
			DP[i][j]=INF;
	DP[0][1]=0;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=k+1; j++)
			{
			DP[i][j]=min(DP[i-1][j-1]+a[i], DP[i-1][j]+b[i]);
			if (DP[i][j]==DP[i-1][j-1]+a[i])
				from[i][j]=1;
			else
				from[i][j]=0;
			DP[i][j]>x ? DP[i][j]=INF:DP[i][j]=max(DP[i][j], 0ll);
			}
	if (!gen) return DP[n][k+1]<INF/2;
	int X=n, Y=k+1;
	while (X!=0)
		ans+='B'-from[X][Y], Y-=from[X][Y], X--;
	return reverse(ans.begin(), ans.end()), 1;
}
int main()
	{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for (int i=1; i<=n; i++)
		cin>>a[i];
	for (int i=1; i<=n; i++)
		cin>>b[i];
	long long low=-1, high=SIZE*(1ll<<30);
	while (low+1!=high)
		{
		long long mid=(low+high)/2;
		if (check(mid))
			high=mid;
		else
			low=mid;
		}
	check(high, 1), cout<<high<<"\n"<<ans<<endl;
	return 0;
	}