전시회

바이토츠카 미술관은 부부 화가 안나 비토츠카와 보구스와프 비토츠키의 그림으로 전시회를 열 계획이다. 이 부부는 특이한 방식으로 작업하는 것으로 알려져 있다. 매주 초에 두 사람은 함께 새 그림의 제목을 고른다. 그런 다음 일주일 내내 각자 따로 작업해서, 같은 제목의 그림 두 점을 만든다. 한 점은 안나가, 다른 한 점은 보구스와프가 그린다. 부부는 이런 방식으로 n주 동안 작업했으므로 그림 n쌍이 있다.

미술관 큐레이터인 당신은 비토츠키 부부와 맺은 전시 계약을 이행해야 한다. 계약에 따르면 매주 한 점씩, 총 n점의 그림을 전시해야 한다. 그림은 긴 벽 한쪽에 왼쪽에서 오른쪽으로, 제작된 순서대로 걸린다. 따라서 왼쪽에서 i번째 그림은 i번째 주에 만들어진 두 점 중 하나여야 한다. 그 주의 두 그림 중 어느 쪽을 걸지는 자유롭게 고를 수 있다. 계약의 유일한 조건은 전시된 그림 중 정확히 k점이 안나의 작품이고, 나머지는 보구스와프의 작품이라는 것이다.

개막을 앞두고 경찰로부터 도둑 무리가 미술관을 털 계획이라는 제보를 받았다. 도둑들은 벽의 연속된 한 구간에 걸린 전시 그림을 모두 훔칠 계획이다. 정수 ℓ과 r을 1 ≤ ℓ ≤ r ≤ n을 만족하도록 고르고, 밤에 ℓ번째부터 r번째까지의 그림을 전부 훔친다. 전시되지 않은 그림은 안전하다. 또한 도둑들이 그림마다 매긴 가치를 알고 있다. 가치는 음수일 수도 있다. 너무 커서 옮기기 어렵거나 나중에 팔기가 거의 불가능한 그림이 있기 때문이다. 도둑 무리의 최종 이익은 훔친 그림 가치의 합이다. 도둑들은 이익이 최대가 되도록 ℓ과 r을 고른다고 가정한다. 이익을 양수로 만들 수 없다면 계획을 포기하고, 최종 이익은 0이다.

당신은 도둑을 막을 수는 없다. 하지만 범행 의욕을 꺾을 수는 있다. 도둑 무리의 최종 이익이 최소가 되도록 그림을 걸고 싶다. 어떤 그림을 걸어야 하는가? 계획이 성공한다면 도둑 무리는 얼마의 이익을 얻게 되는가?

첫 줄에는 두 정수 n과 k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n)가 주어진다. n은 컬렉션에 있는 그림 쌍의 수이고, k는 걸어야 하는 안나의 그림 수이다.

둘째 줄에는 n개의 정수 a_1, ..., a_n ($-10^9 \le a_i \le 10^9$)이 주어진다. a_i는 안나의 i번째 그림의 가치(바이탈라르)이다.

셋째 줄에는 n개의 정수 b_1, ..., b_n ($-10^9 \le b_i \le 10^9$)이 주어진다. 보구스와프의 그림에 대해 같은 방식으로 주어지며, b_i는 보구스와프의 i번째 그림의 가치이다.

두 줄을 출력한다. 첫 줄에는 그림을 최적으로 골랐다고 가정했을 때, 도둑 무리의 최종 이익이 가질 수 있는 최솟값 x (바이탈라르, 0 이상의 정수)를 출력한다.

둘째 줄에는 도둑 무리의 최종 이익을 정확히 x로 만드는 예시 해를 출력한다. n글자 문자열이며, i번째 글자는 i번째로 걸 그림이 안나의 작품이면 A, 보구스와프의 작품이면 B이다. 최적해가 여러 개라면 그중 아무것이나 출력해도 된다.