class Solution {
   private static int answer;

    public static int solution(int k, int[][] dungeons) {
        answer = 0;
        findMaxVisitDungeon(k, dungeons, 0);

        return answer;
    }

    private static void findMaxVisitDungeon(int k, int[][] dungeons, int idx) {
        if (answer == dungeons.length) {
            return;
        }

        if (idx >= dungeons.length) {
            answer = Math.max(answer, visitDungeons(dungeons, k));
            return;
        }

        for (int i = idx; i < dungeons.length; i++) {
            perm(dungeons, idx, i);
            findMaxVisitDungeon(k, dungeons, idx + 1);
            perm(dungeons, idx, i);
        }
    }

    private static void perm(int[][] dungeons, int idx1, int idx2) {
        int[] data1 = dungeons[idx2];
        dungeons[idx2] = dungeons[idx1];
        dungeons[idx1] = data1;
    }

    private static int visitDungeons(int[][] dungeons, int k) {
        int visitCnt = 0;

        for (int i = 0; i < dungeons.length; i++) {
            int[] dungeon = dungeons[i];

            if (dungeon[0] > k) continue;

            k -= dungeon[1];
            visitCnt++;
        }

        return visitCnt;
    }
}