충전소 전력 배분 구조

문제

전기차 충전소 운영 시스템은 설비 구성을 JSON 과 비슷한 한 줄 문자열로 저장한다. 문자열은 중괄호로 감싼 객체이고, 객체는 쉼표로 구분된 항목 0개 이상으로 이루어진다. 항목은 "키:값" 꼴이며 키는 영어 소문자 1~6글자, 값은 0 이상 10^9 이하의 정수 또는 객체이다. 공백과 따옴표는 없다. 같은 객체 안에서 같은 키가 여러 번 나오면 마지막 항목만 남고 앞의 항목은 (값이 객체라면 그 안의 내용까지) 없던 것으로 한다. 남은 항목의 순서는 각 키가 마지막으로 등장한 순서를 따른다. 키 "cap" 은 항상 정수 값을 가지며, 그 객체가 아래쪽에서 받은 전력을 최대 그 값까지만 위로 전달할 수 있다는 뜻이다. 객체에 cap 항목이 없으면 상한이 없다. cap 이 아닌 키의 정수 값은 충전기 한 대의 요구 전력이다. 객체의 입력 전력은 자신의 충전기 요구 전력과 하위 객체가 위로 내보낸 전력의 합이고, 내보내는 전력은 입력 전력과 cap 중 작은 값이다. 가장 바깥 객체가 내보내는 전력을 총 공급량이라 한다. 정리된 구조에서 항목 순서대로 객체 안으로 들어가며 깊이 우선으로 충전기를 세어 1번부터 번호를 붙인다. 충전기 하나를 없앴을 때 총 공급량이 줄어드는 양이 가장 큰 충전기를 구하라. 줄어드는 양이 같으면 번호가 작은 쪽을 택한다. 충전기는 항상 1대 이상 남는다.

입력

한 줄에 문자열 하나가 주어진다. 문자열의 길이는 1 이상 400,000 이하이며 위 문법을 지킨다. 최상위 값은 객체이고, cap 의 값은 0 이상 10^9 이하의 정수이다.

출력

첫째 줄에 총 공급량을 출력한다. 둘째 줄에 줄어드는 양이 가장 큰 충전기의 번호와 그때 줄어드는 양을 공백으로 구분해 출력한다. 줄어드는 양이 모두 0이면 번호는 1이다.

{cap:100,a:{cap:30,x:20,y:25},b:40,c:{z:10}}

80
3 40

{a:5,b:{p:3,cap:2,p:7},a:9,cap:50,cap:8}

8
2 6

{a:{},cap:0,b:1}

0
1 0

출처: Devin.KR 자체 제작