#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; #define mid ((left+right)>>1) int n,k; int arr[250023],brr[250023]; ll pref[250023]; ll dp[250023],dp2[250023]; vector<vector<int>>child; int ans[250023]; void dfs(int w,int h){ if(w==0)return; if(child[w][h]&2){ ans[w]=1; dfs(w-1,h-1); child[w][h]-=2; } if(child[w][h]&1){ dfs(w-1,h); child[w][h]-=1; } } int main(){ ios_base::sync_with_stdio(23^23);cin.tie(NULL); cin>>n>>k; child.resize(n+1,vector<int>(k+1,0)); for(int i=1;i<=n;i++){ cin>>arr[i]; pref[i]=pref[i-1]+arr[i]; } for(int i=1;i<=n;i++){ cin>>brr[i]; } for(int i=0;i<=k;i++){ dp[i]=-1e18; dp2[i]=-1e18; } dp[0]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=k;j++){ if(dp[j]>dp2[j]){ child[i][j]=0; } dp2[j]=max(dp2[j],dp[j]); if(dp[j]==dp2[j]){ child[i][j]+=1; } ll ek=brr[i]; if(j==0)ek+=pref[i-1]; if(j+1==k)ek-=pref[i]; if(j!=k){ dp2[j+1]=max(dp2[j+1],dp[j]+ek); child[i][j+1]=2; } } for(int j=0;j<=k;j++){ swap(dp2[j],dp[j]); dp2[j]=-1e18; } } cout<<dp[k]<<endl; return 0; dfs(n,k); for(int i=1;i<=n;i++){ cout<<ans[i]; } cout<<endl; }