스마트 홈의 공통 점검 시각

문제

한 스마트 홈에서는 여러 기기의 상태를 한꺼번에 확인하는 공통 점검을 하루에 한 번 진행하려 한다. 점검 시작 시각은 0시부터 23시까지의 정각 중 하나로 정해야 한다. 각 기기는 점검하기를 선호하는 시각과 그 선호를 얼마나 중요하게 반영할지를 나타내는 가중치를 가지고 있다. 관리 장치는 모든 기기의 불편 점수 합이 가장 작아지는 시각을 찾으려 한다. 하루의 시각은 원형으로 이어진다고 본다. 두 시각 a와 b 사이의 거리는 정방향과 역방향 중 더 짧게 이동하는 데 필요한 시간 수다. 구체적으로 d를 |a-b|라고 할 때 거리는 d와 24-d 중 작은 값이다. 예를 들어 23시와 1시 사이의 거리는 2이고, 6시와 18시 사이의 거리는 12다. 어느 쪽으로 이동하는지는 점수에 영향을 주지 않는다. 기기 i가 선호하는 시각을 h_i, 가중치를 w_i라고 하자. 공통 점검을 t시에 시작하면 이 기기의 불편 점수는 t와 h_i 사이의 거리에 w_i를 곱한 값이다. 전체 불편 점수는 모든 기기의 불편 점수를 더한 값이다. 선호 시각이나 가중치가 같은 기기가 여러 개 있어도 각각의 점수를 모두 더한다. 다만 집 안의 다른 예약 때문에 점검을 시작할 수 없는 시각이 있을 수 있다. 입력에는 24개 시각 각각에 대해 점검을 시작할 수 있는지가 주어진다. 시작할 수 없는 시각은 점수가 아무리 작아도 선택할 수 없다. 점검의 지속 시간이나 다른 시각과의 겹침은 고려하지 않으며, 시작 시각의 허용 여부만 확인한다. 허용된 시각 중 전체 불편 점수가 가장 작은 시각을 구한다. 최소 점수가 같은 시각이 여러 개라면 시각을 나타내는 정수가 가장 작은 것을 선택한다. 허용된 시각이 하나도 없다면 점검 시각을 정할 수 없다고 보고한다.

입력

첫째 줄에 기기 수인 정수 N이 주어진다. 1 ≤ N ≤ 30,000이다.
둘째 줄에 길이가 정확히 24인 문자열이 주어진다. 각 문자는 0 또는 1이다. 왼쪽에서 t+1번째 문자가 1이면 t시에 점검을 시작할 수 있고, 0이면 시작할 수 없다. 여기서 0 ≤ t ≤ 23이다.
다음 N개의 줄에 정수 h_i와 w_i가 주어진다. 0 ≤ h_i ≤ 23이고 1 ≤ w_i ≤ 9이다.

출력

허용된 시각이 있으면 선택한 시각과 그 시각의 전체 불편 점수를 공백으로 구분하여 한 줄에 출력한다. 허용된 시각이 하나도 없으면 -1만 출력한다.

3
111111111111111111111111
23 1
1 1
0 1

0 2

2
111111111111111111111111
4 2
6 2

4 4

1
000000000000000000000000
12 9

-1

출처: Devin.KR 자체 제작