노선 묶음의 승객 합계

문제

버스 운영 시스템의 백엔드에서는 여러 정류장의 승차 인원을 묶음 단위로 관리한다. 하나의 묶음에는 정류장 기록과 다른 묶음이 함께 들어갈 수 있다. 담당자는 중첩된 기록을 받아 승객 합계가 기준 이상인 묶음의 개수를 구하려 한다. 기록은 JSON과 비슷하지만 이 문제에서 정한 문법만 사용하는 문자열이다. 묶음은 중괄호로 둘러싸며, 내부에는 쉼표로 구분한 항목을 0개 이상 넣는다. 각 항목은 큰따옴표로 감싼 키, 콜론, 값 순서로 적는다. 키는 영문 소문자 1개 이상 8개 이하로 이루어진다. 값은 정류장의 승차 인원을 나타내는 음이 아닌 정수이거나 또 다른 묶음이다. 같은 묶음 안에서도 키가 반복될 수 있으며, 키가 같은 항목도 모두 별개의 기록으로 취급한다. 어떤 묶음의 승객 합계는 그 묶음 내부에 직접 적힌 모든 정수와, 내부의 다른 묶음에 들어 있는 모든 정수를 합한 값이다. 따라서 하나의 정류장 기록은 자신을 포함하는 여러 묶음의 합계에 각각 반영된다. 정수 값 자체는 묶음이 아니므로 개수를 셀 때 포함하지 않는다. 가장 바깥쪽 묶음도 하나의 묶음으로 센다. 빈 묶음의 승객 합계는 0이다. 묶음의 이름이나 정류장 키는 합계 계산에 영향을 주지 않는다. 예를 들어 어떤 하위 묶음의 합계가 기준에 도달하더라도 그 안의 정수를 상위 묶음의 계산에서 빼지 않는다. 입력에 등장하는 모든 묶음을 각각 독립적으로 판정해야 한다. 주어진 기준 K 이상인 승객 합계를 가진 묶음의 개수를 출력한다. 조건을 만족하는 묶음이 없으면 0을 출력한다.

입력

첫째 줄에 정수 K가 주어진다. 0 ≤ K ≤ 1,000,000,000이다.
둘째 줄에 기록 문자열 S가 주어진다. 2 ≤ |S| ≤ 200,000이다. S에는 공백이 없으며, 가장 바깥쪽 값은 반드시 묶음이다. 모든 키는 영문 소문자 1개 이상 8개 이하이고, 정수 값은 0 이상 1,000,000 이하이다. 정수는 0 자체를 제외하면 앞에 0이 붙지 않는다. 문자열은 지문에 설명한 문법을 만족한다. 중첩 깊이에는 문자열 길이로부터 정해지는 제한 외에 별도 제한이 없다.

출력

승객 합계가 K 이상인 묶음의 개수를 정수 하나로 출력한다. 가장 바깥쪽 묶음도 포함한다.

5
{"east":{"a":3,"b":4},"west":{"c":2},"d":1}

2

0
{"a":{},"b":{"c":0}}

3

10
{"a":2,"a":{"b":3}}

0

출처: Devin.KR 자체 제작