/// - art -
#include <bits/stdc++.h>
#define el cout << '\n'
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c) for (int i = 0, _c = (c); i < _c; ++i)
const int N = 25e4 + 7;
using namespace std;
int n, k;
int buy[N], sell[N];
///-----------
long long profit;
int base = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> k_largest;
priority_queue<pair<int, int>> remains;
int pick[N];
void ADD(int i) {
profit -= buy[i];
if (base < k) {
profit += sell[i];
k_largest.emplace(sell[i], i);
pick[i] = 2;
++base;
return;
}
while (!k_largest.empty() && pick[k_largest.top().second] != 2) {
k_largest.pop();
}
assert(!k_largest.empty());
auto [sell_j, j] = k_largest.top();
if (sell_j < sell[i]) {
pick[j] = 1;
pick[i] = 2;
k_largest.pop();
k_largest.emplace(sell[i], i);
remains.emplace(sell_j, j);
profit += sell[i] - sell_j;
}
else {
pick[i] = 1;
remains.emplace(sell[i], i);
}
}
void DEL(int i) {
profit += buy[i];
if (pick[i] == 2) {
while (!remains.empty() && pick[remains.top().second] != 1) {
remains.pop();
}
assert(!remains.empty());
auto [sell_j, j] = remains.top(); remains.pop();
k_largest.emplace(sell_j, j); pick[j] = 2;
profit += sell_j - sell[i];
}
pick[i] = 0;
}
int cur_l, cur_r;
long long calc(int L, int R) {
while (cur_r < R) {
++cur_r; ADD(cur_r);
}
while (cur_l > L) {
--cur_l; ADD(cur_l);
}
while (cur_r > R) {
DEL(cur_r); --cur_r;
}
while (cur_l < L) {
DEL(cur_l); ++cur_l;
}
return profit;
}
int opt[N];
long long dp[N];
void compute(int l, int r, int optL, int optR) {
if (l > r) {
return;
}
int mid = (l + r) / 2;
opt[mid] = optR;
// cout << calc(1, 3), el;
FOR (i, max(mid + k - 1, optL), optR) {
if (dp[mid] < calc(mid, i)) {
dp[mid] = calc(mid, i);
opt[mid] = i;
}
}
// cout << calc(1, 3) << ' ' << calc(1, 3), el;
// cout << l << ' ' << r << ' ' << optL << ' ' << optR << ' ' << dp[mid] << ' ' << mid << ' ' << opt[mid] << ' ' << calc(1, 3), el;
compute(l, mid - 1, optL, opt[mid]);
compute(mid + 1, r, opt[mid], optR);
}
/// ---------
vector<int> Open[N], Close[N];
int main() {
#define name "art"
if (fopen(name".inp", "r")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
FOR (i, 1, n) {
cin >> buy[i];
}
FOR (i, 1, n) {
cin >> sell[i];
}
// cout << calc(1, 4), el;
// return 0;
memset(dp, -0x3f, sizeof dp);
cur_l = 1; cur_r = 0;
compute(1, n, 1, n);
long long max_profit = *max_element(dp + 1, dp + n + 1);
// cout << max_profit, el;
// return 0;
int last = n;
REV (i, n, 1) if (dp[i] == max_profit) {
// cout << i << ' ';
REV (j, last, opt[i]) if (calc(i, j) == max_profit) {
while (!k_largest.empty() && pick[k_largest.top().second] != 2) {
k_largest.pop();
}
assert(!k_largest.empty());
Open[i].emplace_back(k_largest.top().first);
Close[j + 1].emplace_back(k_largest.top().first);
}
last = opt[i];
}
multiset<int> ms;
cout << max_profit, el;
FOR (i, 1, n) {
for (int &x: Open[i]) {
ms.insert(x);
}
for (int &x: Close[i]) {
ms.erase(ms.lower_bound(x));
}
cout << (!ms.empty() && sell[i] >= *ms.begin());
}
return 0;
}
