페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6057

피자왕 비룡 1초 1024MB

문제

피자왕 비룡은 피자가게를 운영하고 있다. 비룡이의 피자가게는 총 P가지 종류의 피자를 판매한다.

비룡이는 피자를 안만들면 몸이 근질거리는 체질이라 주문이 들어오던 말던 피자를 만들고 싶으면 만들어 놓는다.

  • 완성된 i번째 피자는 p_i 종류이며, 가격은 m_i이다.

그러다가 피자 주문이 들어오면 주문이 들어온 종류의 피자 중 가장 먼저 만들어 놓은 피자를 손님에게 제공한다.

  • 주문이 들어온 i번째 피자의 종류는 p_i이다.

  • 만약 해당 p_i 종류의 피자가 만들어져 있지 않다면 손님은 실망하여 가게를 떠나게 된다. (무시된다)

오늘 하루 영업하는 동안 이루어진 총 N번의 피자 생산과 주문이 순서대로 주어졌을 때, 오늘 비룡이의 피자가게 매출을 알아보자.


입력

첫 줄에 두 정수 P와 N이 주어진다. (1 \le P \le 50, \space 1 \le N \le 500,000)

두 번째 줄부터 N줄에 걸쳐 cmd_i와 p_i와 m_i 또는 cmd_i와 p_i가 주어진다. (cmd_i \in \{0,1\}, \space 1 \le p_i \le P,\space 1 \le m_i \le 100)

  • cmd_i가 0이면 피자 제작으로 p_i 종류이며 가격이 m_i원인 피자가 만들어진다.

  • cmd_i가 1이면 피자 주문으로 p_i 종류의 피자가 주문된다.


출력

오늘 비룡이의 피자가게 매출을 출력한다.


부분문제

번호 점수 조건
#130점

P =1

#230점

P=2

#340점

추가 제한 없음


예제1

입력
39
11
0331
0165
0151
13
0159
11
13
0139
출력
96

태그

출처

@klee

역링크