급행열차의 정차역 고르기

문제

지하철 노선 하나에 N개의 역이 일직선 위에 놓여 있다. 역에는 시작점에서 가까운 순서대로 1번부터 N번까지 번호가 붙어 있고, i번 역은 시작점에서 x_i 미터 떨어진 곳에 있다. x_1 < x_2 < ... < x_N 이 성립한다.\n\n이 노선에 급행열차를 하나 운행하려 한다. 급행열차는 1번 역에서 출발해 N번 역에서 끝나며, 도중에 정차할 역을 골라야 한다. 1번 역과 N번 역에는 항상 정차한다. 또한 일부 역은 환승객 때문에 필수 정차역으로 지정되어 있으며, 필수 정차역에는 반드시 정차해야 한다. 정차하는 역의 수는 1번 역과 N번 역을 포함하여 K개 이하여야 한다.\n\n정차한 역들을 번호 순서로 나열했을 때 이웃한 두 정차역 사이의 거리 중 가장 큰 값을 최대 무정차 거리라 한다. 위 조건을 모두 만족하도록 정차역을 고를 때, 최대 무정차 거리의 최솟값을 구하여라. 조건을 만족하는 선택이 하나도 없으면 -1을 출력한다.

입력

첫째 줄에 정수 N과 K가 주어진다. (2 ≤ N ≤ 200,000, 2 ≤ K ≤ N)\n둘째 줄에 x_1, x_2, ..., x_N 이 공백으로 구분되어 주어진다. (0 ≤ x_1 < x_2 < ... < x_N ≤ 10^9, 정수)\n셋째 줄에 길이 N인 문자열 f가 공백 없이 주어진다. f의 i번째 문자가 1이면 i번 역이 필수 정차역이고 0이면 아니다. 1번과 N번 역은 f의 값과 관계없이 항상 정차한다.

출력

최대 무정차 거리의 최솟값을 한 줄에 출력한다. 조건을 만족하는 선택이 없으면 -1을 출력한다.

5 3
0 3 4 9 10
00000

6

5 3
0 3 4 9 10
00010

9

3 2
0 5 6
010

-1

출처: Devin.KR 자체 제작