최대 HP

당신은 게임 "마비노기 영웅전"의 전투 로그 분석을 맡게 되었다. 이번에 분석할 전투는 마법 전문가인 이비의 전투이다.

이비는 몬스터와 전투를 했고, 이 때 전투 과정에서 발생하는 게임 로그인 전투 로그는 시작 체력과 여러 개의 턴으로 이루어져 있다. 그리고 각 턴 마다 다음의 로그가 한 줄에 하나씩 기록되어있다.

• 이비가 데미지를 받는다. 이 턴 이후에 체력이 h 만큼 줄어든다. 단, 데미지를 받아서 체력이 $0$ 이하가 되는 경우는 없었다. 이 로그는 1 h 형태로 기록된다.
• 이비가 "회복" 스킬을 사용한다. 이 턴 이후에 체력이 h만큼 회복된다. 단, 회복을 해서 최대 체력을 넘어가는 경우는 없었다. 이 로그는 2 h 형태로 기록된다.
• 이비가 "최대 생명력" 스킬을 사용한다. 이 턴 이후에 체력이 h만큼 회복되어 최대 체력이 된다. 이 로그는 3 h 형태로 기록된다.

이비의 최대 체력은 처음부터 정해져 있으며 변하지 않았다. 이 로그들을 분석하여 이비의 최대 체력이 얼마인지 알아보자.

입력 형식

첫째 줄에 시작 체력 $H$와 진행한 턴 수 $T$가 공백으로 구분되어 주어진다. ($1 \le H \le 100$; $3 \le T \le 100$)

다음 $T$개의 줄에는 로그의 종류를 뜻하는 $a$, 데미지의 양 혹은 회복된 양을 뜻하는 $h$가 공백으로 구분되어 주어진다. 로그에 대한 설명은 본문과 같다. ($1 \le a \le 3$; $1 \le h \le 100$)

입력으로 주어지는 모든 수는 자연수이고, 모든 로그는 올바르다는 것이 보장되며, 각 종류의 로그가 최소 한 개 이상 들어온다는 것이 보장된다.

출력 형식

분석한 이비의 최대 체력을 첫째 줄에 출력한다.

예제 1

10 3
2 20
1 10
3 40

60

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설