트릭 오브 더 트레이드

예술품 도둑으로서의 경력이 기대만큼 화려하지 않아서, 이제 올해 CEOI*의 메달을 노리기로 했습니다. 지금까지 계획은 의도대로 진행되고 있습니다. 위원회는 여러분이 일으킨 석유 부족 사태에 아직 혼란스러워하고 있으며, 가짜 해킹 시도에 바로 속아 넘어갔습니다. 재심사 계획을 세우도록 비밀 본부에 들어가게 되었고, 그곳에서 메달이 보관된 금고의 조합을 쉽게 알아냈습니다.

하지만 다음 단계에는 조수가 필요한데, 조수를 고용할 돈이 부족합니다. 마침 해결 방법을 찾았습니다. 베를린의 한 가게가 프로그래밍 가능한 로봇 청소기 $N$대를 팝니다. 로봇은 $1$번부터 $N$번까지 번호가 붙어 있습니다. $i$번 로봇의 가격은 $c_i$유로입니다. 판매자는 연속된 로봇 구간 전체만 팝니다. 로봇 $i$번과 $j$번을 사면, $i \le k \le j$인 모든 로봇 $k$를 함께 사야 합니다.

여러분은 동료 참가자들에게 이 로봇 중 $K$대를 판매하기로 약속했습니다 ($1 \le K \le N$). 참가자들은 로봇 $i$번에 $s_i$유로를 지불하며, 여러분은 이익을 크게 남기기를 바랍니다.

다음을 수행하는 프로그램을 작성하시오.

• 적어도 $K$대 이상의 구간을 사고, 그 구간에서 정확히 $K$대를 판매해서 얻을 수 있는 최대 이익을 구한다.
• 최대 이익을 내는 거래 중 하나에서 판매될 수 있는 로봇을 구한다.

• 당연히 문제는 예술품에 있었지, 도난에 있었던 것이 아닙니다.

결국 여러분이 가지고 있는 로봇도 쓸모가 있을지 모릅니다...

첫 줄에 정수 $N$과 $K$가 주어진다. 둘째 줄에는 정수 $c_1, \dots, c_N$이 주어지고, 셋째 줄에는 정수 $s_1, \dots, s_N$이 주어진다.

두 줄을 출력한다. 첫째 줄에는 얻을 수 있는 최대 이익을 정수 하나로 출력한다. 둘째 줄에는 길이가 $N$인 이진 문자열을 출력한다. $i$번째 문자가 $1$이면 최대 이익을 내는 어떤 거래에서 $i$번 로봇을 판매할 수 있고, $0$이면 그렇지 않다.

첫 번째 예시에서는 $3$번부터 $5$번 로봇을 사서 세 대를 모두 판매할 수 있다. 비용은 $2 + 3 + 6 = 11$유로이고, 참가자들은 이 로봇들에 $5 + 2 + 3 = 10$유로를 지불하므로 1유로 손해를 본다. 다른 구간을 사면 손해가 더 커진다.

두 번째 예시에서는 $1$번부터 $3$번 로봇을 사서 $1$번과 $3$번을 판매할 수 있다. 비용은 $8$유로이고 참가자들은 $10$유로를 지불하므로 이익은 $2$유로다. 다른 구간은 이보다 높은 이익을 내지 못한다. $3$번과 $4$번을 사서 둘 다 판매하거나, $3$번부터 $5$번 로봇을 사서 $3$번과 $5$번을 판매하는 방법도 있다. 두 경우 모두 이익은 $2$유로다. 따라서 $2$번 로봇을 제외한 모든 로봇이 최대 이익 거래에 포함될 수 있다.