아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

영웅

시간 제한1초메모리 제한256 MB

요약
체력 z로 n마리 괴물을 모두 쓰러뜨리는 순서를 찾아 가능하면 TAK과 순서를, 불가능하면 NIE를 출력합니다.
난이도

보통10점 중 6점

유형
그리디, 정렬
정답자
아직 제출이 없습니다

문제

Bitor은 초기 체력 z로 n마리 몬스터를 순서대로 싸워 물리쳐야 한다. i번 몬스터는 d_i 피해를 주고 쓰러뜨리면 a_i 체력을 회복한다. 싸우는 동안 체력이 0 이하가 되면 안 된다. 가능한지 판별하고, 가능하면 승리 순서 하나를 출력하라.

입력

첫 줄에 n과 z. 다음 n줄에 각 몬스터의 d_i, a_i.

출력

불가능하면 NIE. 가능하면 첫 줄 TAK, 둘째 줄에 1..n의 순열.

제한

  • 1≤n,z≤100,0001 \leq n, z \leq 100{,}000

예제1

  1. 예제 1

    입력
    3 5
3 1
4 8
8 3
    예상 출력
    TAK
2 3 1