모든 입력 값은 양의 정수이다. 연결점의 수를 N이라고 하고 폭약의 수를 M이라고 하자. (1 ≤ N+M ≤ 300,000)

각 연결점은 1부터 N까지의 자연수로 번호가 붙어 있다. 스위치는 항상 1번 연결점이다. 각 폭약은 N+1부터 N+M까지의 자연수로 번호가 붙어 있다.

입력은 다음과 같은 형태로 주어진다:

N M

P₂ C₂

P₃ C₃

...

P_N C_N

P_N+1 C_N+1

...

P_N+M C_N+M

각 P_i(1 ≤ P_i ≤ i)는 i번 연결점 혹은 폭약이 도화선으로 연결되어 있는 연결점의 번호이다.

C_i는 해당 도화선의 길이이다(1 ≤ C_i ≤ 10⁹). 1번 연결점을 제외한 모든 연결점에는 2개 이상의 도화선이 연결되어 있다. 모든 폭약에는 단 하나의 도화선이 연결되어 있다.

Firework timer 1s memory 128MB

Firework 1s 128MB