한 줄을 비우는 상영관

문제

한 영화관은 특별 상영을 준비하면서 한 줄에 놓인 좌석 중 연속한 K개를 장비 설치 구역으로 사용하려 한다. 이 줄에는 N개의 좌석이 있으며, 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 좌석의 상태는 길이가 N인 문자열로 주어진다. 문자열의 i번째 문자가 0이면 i번 좌석은 비어 있고, 1이면 관객이 앉아 있다. 모든 좌석은 같은 줄에 있으며, 마지막 좌석과 첫 좌석은 서로 이어져 있지 않다. 설치 구역은 반드시 원래 좌석 번호가 연속한 K개 좌석으로 정해야 한다. 구역을 정한 뒤에는 그 안에 앉아 있는 관객을 모두 다른 줄로 안내한다. 다른 줄에는 충분한 자리가 있으므로 이동할 관객 수 외의 조건은 고려하지 않는다. 구역 밖의 관객은 이동하지 않으며, 비어 있는 좌석에는 아무 작업도 하지 않는다. 따라서 어떤 구역을 선택할 때 필요한 이동 인원은 그 구역에 들어 있는 문자 1의 개수와 같다. 영화관은 이동하는 관객 수가 가장 적은 구역을 선택하려 한다. 이동 인원이 같은 구역이 여러 개라면 시작 좌석 번호가 가장 작은 구역을 선택한다. 선택할 수 있는 시작 번호는 1 이상 N-K+1 이하의 정수다. 구역은 정확히 K개의 좌석을 포함해야 하며, 중간 좌석을 건너뛰거나 줄의 양 끝을 연결해서는 안 된다. 선택한 구역의 시작 좌석 번호와 이동할 관객 수를 구하는 프로그램을 작성한다. 모든 좌석이 비어 있으면 시작 번호가 1인 구역을 선택하고 이동 인원은 0이다. 모든 좌석에 관객이 있어도 같은 선택 규칙을 적용한다. K는 N 이하이므로 선택 가능한 구역은 항상 하나 이상 존재한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다.
둘째 줄에 문자 0과 1로만 이루어진 길이 N의 문자열이 주어진다. 각 문자는 왼쪽부터 해당 좌석의 상태를 나타낸다.

출력

선택한 구역의 시작 좌석 번호와 이동할 관객 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

8 3
11000101

3 0

5 2
10101

1 1

4 4
0000

1 0

출처: Devin.KR 자체 제작