드래곤 앤 던전
시간 제한1초메모리 제한256 MB
공격력이 고정된 던전을 순서대로 시뮬레이션하며 필요한 체력을 기록한 뒤, 최대 체력을 이분 탐색으로 찾아 생존 가능한 최솟값을 구합니다.
문제
용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 했다. 우선 용사는 자신과 던전을 분석했다.
용사에게는 세 종류의 능력치가 있다.
- HMaxHP : 용사의 최대 생명력이다. 이 값은 1 이상이어야 하며 던전에 들어간 이후로 변하지 않는다.
- HCurHP : 용사의 현재 생명력이다. 던전에 들어가기 전 이 값은 최대 생명력 HMaxHP와 같다. 이 값은 HMaxHP보다 커질 수 없다.
- HATK : 용사의 공격력이다.
던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동할 수 있다. 방에는 포션이 있거나 몬스터가 있는데, 몬스터가 있을 경우 몬스터를 쓰러트려야 다음 방으로 이동할 수 있다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있다.
몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행된다.
- 용사의 공격력 HATK만큼 몬스터의 생명력을 깎는다.
- 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동한다.
- 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎는다.
- 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망한다.
- 다시 1부터 진행한다.
포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 HCurHP가 일정량 회복되고 공격력 HATK도 일정량만큼 증가된다. 회복된 생명력이 최대 생명력 HMaxHP보다 큰 경우 용사의 현재 생명력 HCurHP는 최대 생명력 HMaxHP와 같아진다.
용사는 던전으로 향하기 전에 만반의 준비를 하고 있다. 용사는 수련을 하면 최대 생명력 HMaxHP를 늘릴 수 있는데 얼마나 수련해야 할지 고민이다.
용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 여러분이 계산해주면 좋겠다고 한다.
입력
첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456)과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000)가 주어진다.
i+1번째 줄에는 i번째 방의 정보를 나타내는 세 개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 ≤ ai, hi ≤ 1,000,000)가 주어진다.
ti가 1인 경우 공격력이 ai이고 생명력이 hi인 몬스터가 있음을 나타내고, ti가 2인 경우 용사의 공격력 HATK를 ai만큼 증가시켜주고 용사의 현재 생명력 HCurHP를 hi만큼 회복시켜주는 포션이 있음을 나타낸다.
출력
용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 출력한다.