서가 설정의 상속

문제

한 도서관의 백엔드는 서가의 대여 한도를 중첩된 설정 문서로 관리한다. 큰 서가 안에는 작은 서가가 들어갈 수 있으며, 가장 바깥 서가 하나가 도서관 전체의 구조를 감싼다. 설정 문서는 JSON과 비슷한 형식이지만, 이 문제에서 정한 두 종류의 객체만 사용한다. 각 객체는 서가 하나를 나타내며, 키 c의 값인 배열에는 그 서가에 바로 속한 작은 서가들이 순서대로 들어 있다. 객체의 형식은 {"c":[자식 목록]} 또는 {"v":정수,"c":[자식 목록]}이다. 자식 목록이 비어 있으면 대괄호 안에 아무것도 쓰지 않는다. 자식이 여러 개이면 객체 사이를 쉼표로 구분한다. 키 v가 있으면 반드시 c보다 먼저 나오며, 다른 키는 없다. 문서 전체에는 공백, 줄바꿈, 음수, 문자열 값이 나타나지 않는다. 키에 사용하는 큰따옴표와 각 구두점은 생략할 수 없다. 각 서가에는 실제로 적용되는 대여 한도가 있다. 키 v가 있는 서가는 그 정수를 자신의 한도로 사용한다. 키 v가 없는 서가는 바로 바깥 서가의 적용 한도를 그대로 물려받는다. 가장 바깥 서가에 v가 없으면 그 서가의 적용 한도는 0이다. 한 서가에서 지정한 값은 그 서가의 자손에게만 전달된다. 따라서 어떤 자식 서가에서 값을 바꾸어도 그 형제 서가에 적용되는 값은 바뀌지 않는다. 값 0을 지정한 경우도 값을 생략한 경우와 구별해야 한다. 자식이 없는 서가를 말단 서가라고 한다. 운영 담당자는 모든 말단 서가에 적용되는 한도의 합을 알고 싶다. 자식이 있는 서가의 한도는 합에 직접 더하지 않는다. 문서에 객체가 하나뿐이면 가장 바깥 서가가 곧 말단 서가다. 중첩 깊이가 매우 클 수 있으므로, 입력 문서를 끝까지 해석하면서 각 말단 서가가 어떤 값을 물려받는지 정확하게 계산해야 한다.

입력

첫째 줄에 설정 문서 하나가 주어진다. 문서는 지문에서 정의한 형식에 맞으며 길이는 8 이상 400,000 이하이다. 객체 수는 1 이상 200,000 이하이다. 모든 v의 값은 0 이상 1,000,000 이하의 정수이며, 0을 제외하면 앞에 불필요한 0이 붙지 않는다. 중첩 깊이에는 별도 제한이 없다.

출력

모든 말단 서가에 적용되는 한도의 합을 정수 하나로 출력한다.

{"v":6,"c":[{"c":[]},{"v":2,"c":[{"c":[]},{"v":0,"c":[]}]},{"c":[]}]}

14

{"c":[{"v":9,"c":[]},{"c":[]}]}

9

{"v":7,"c":[]}

7

출처: Devin.KR 자체 제작