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
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <vector>
#include <iostream>
#include <array>
#include <cinttypes>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <assert.h>
using namespace std;
namespace wzor 
{
	struct DP_VAL
	{
		int64_t value;
		bool has_used_token;
	};
}
pair<int64_t, std::string> solve_wzor(int n, int k, int *input1, int *input2)
{
	using namespace wzor;
	vector<vector<DP_VAL>> dp(n + 1, vector<DP_VAL>(k + 1));
	input1 -= 1;
	input2 -= 1;
	dp[0][0] = {0, false};
	const int64_t inf = 1e17;
	for(int i = 1; i <= k; ++i)
		dp[0][i] = {(int64_t)inf, false};

	auto can_sum_be_achieved_dp = [&](int64_t sum_to_achieve) -> bool
	{
		for(int i_n = 1; i_n <= n; ++i_n)
		{
			for(int i_k = 0; i_k <= k; ++i_k)
			{
				//dp[i_n][i_k]  what is the smallest value thieves can steal
				int64_t variant_no_token = max(dp[i_n - 1][i_k].value + input2[i_n], (int64_t)0);
				if(dp[i_n - 1][i_k].value >= inf)
					variant_no_token = inf;
				if(i_k == 0)
				{
					dp[i_n][i_k] = {variant_no_token, false};
				}
				else
				{
					int64_t variant_with_token = max(dp[i_n - 1][i_k - 1].value + input1[i_n], (int64_t)0);
					if(dp[i_n - 1][i_k - 1].value >= inf)
						variant_with_token = inf;
					dp[i_n][i_k] = {min(variant_no_token, variant_with_token), variant_no_token > variant_with_token};
				}
				if(dp[i_n][i_k].value >= sum_to_achieve) 
					dp[i_n][i_k].value = inf;
			}
		}
		/*cout << "RUNNING DP: " << sum_to_achieve << ' ' << (dp[n][k].value >= sum_to_achieve) << "\n";
		for(int i = 0; i <= n; ++i)
		{
			for(int j = 0; j <= k; ++j) 
				cout << dp[i][j].value << ' ';
			cout << '\n';
		}*/
		return dp[n][k].value >= sum_to_achieve;
	};
	
	int64_t a = 1, b = 1e16;
	while(a < b)
	{
		int64_t mid = a + (b - a) / 2;
		if(can_sum_be_achieved_dp(mid))
		{
			a = mid + 1;
		}
		else
		{
			b = mid;
		}
	}
	int64_t smallest_sum_thieves_cant_achieve = a;
	assert(can_sum_be_achieved_dp(smallest_sum_thieves_cant_achieve) == false);
	//std::cout << "XD: " << smallest_sum_thieves_cant_achieve << "\n";
	std::string ans;
	int i_k = k;
	int64_t ans_val = 0;
	int64_t current_counter = 0;
	for(int i_n = n; i_n > 0; --i_n)
	{
		if(dp[i_n][i_k].has_used_token)
		{
			current_counter += input1[i_n];
			--i_k;
			ans.push_back('A');
		}
		else
		{
			current_counter += input2[i_n];
			ans.push_back('B');
		}
		current_counter = max(current_counter, (int64_t)0);
		ans_val = max(ans_val, current_counter);
	}
	reverse(ans.begin(), ans.end());
	return {ans_val, ans};
}
#include <iostream>

int input1[100100], input2[100100];
int main()
{
	int n, k;
	std::cin >> n >> k;
	for(int i = 0; i < n; ++i) 
		std::cin >> input1[i];

	for(int i = 0; i < n; ++i) 
		std::cin >> input2[i];

	auto [value, answer] = solve_wzor(n, k, input1, input2);
	std::cout << value << '\n' << answer << '\n';
}