창구 개시 배치의 지연

문제

가상의 은행에서 창구 시스템을 운영하는 DevOps 담당자는 영업 시작 전에 실행할 배치 작업을 정리한다. 작업은 하나의 실행기에서 처리하며, 각 작업의 실행 시간은 정확히 1이다. 시각 0부터 작업을 시작하고, 동시에 둘 이상의 작업을 실행할 수 없다. 실행 중인 작업을 중단할 수 없으며, 작업 사이에 쉬는 시간을 넣는 것은 허용한다. 배치의 의존성은 순서가 있는 이진 트리로 주어진다. 각 정점이 하나의 작업이며, 자식이 있는 작업은 반드시 두 자식을 가진다. 부모 작업이 끝나야 그 자식 작업을 시작할 수 있다. 서로 조상과 자손이 아닌 작업 사이에는 추가 의존성이 없다. 트리에서 먼저 루트를 방문하고, 이어서 왼쪽 부분 트리와 오른쪽 부분 트리를 방문하는 순서로 작업 번호를 1부터 N까지 붙인다. 트리는 길이 N의 영문 문자열 S로 압축되어 있다. S의 i번째 문자는 i번 작업을 나타낸다. 대문자는 자식이 없는 작업이고, 소문자는 두 자식이 있는 작업이다. 문자의 대소문자를 무시했을 때 A 또는 a의 등급은 0, B 또는 b의 등급은 1이며, 같은 방식으로 Z 또는 z의 등급은 25이다. 작업 i의 등급을 g_i라 하면, 운영 기준에 따른 완료 기한은 B×g_i이다. 기한이 0인 작업도 입력에 포함될 수 있다. 작업 i의 실제 완료 시각이 C_i이면 그 작업의 지연은 max(0, C_i−B×g_i)이다. 담당자는 모든 작업의 지연 중 가장 큰 값을 최대한 작게 만들려고 한다. 의존성을 지키면서 모든 작업을 실행할 때 가능한 최대 지연의 최솟값을 구한다. 같은 최솟값을 만드는 실행 순서가 여러 개라면 어느 것을 사용해도 되며, 실행 순서 자체는 출력하지 않는다. 입력은 항상 올바른 트리를 나타내므로 모든 작업을 실행하는 순서가 존재한다.

입력

첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다. N은 홀수이며 1≤N≤199,999이고, 0≤B≤N이다.
둘째 줄에 영문 대문자와 소문자로만 이루어진 길이 N의 문자열 S가 주어진다. S는 지문에서 정의한 방문 순서로 기록된 하나의 올바른 트리를 나타낸다. 즉, 대문자 정점은 자식이 없고 소문자 정점은 정확히 두 자식을 가진다.

출력

가능한 최대 지연의 최솟값을 정수 하나로 출력한다.

3 1
aBC

1

7 1
caABbCD

4

1 1
Z

0

출처: Devin.KR 자체 제작