캐릭터 경험치

캐릭터가 컨텐츠를 수행하고 경험치를 얻어 성장하는 모바일 게임이 있다. 제공된 컨텐츠 마다 이를 수행하기 위해 필요한 스태미나 소모량과 이 컨텐츠를 수행할 경우 얻을 수 있는 경험치가 정해져 있다. 이 게임에서 캐릭터는 자신이 보유하고 있는 스태미나로 제공된 컨텐츠들을 수행하여 경험치를 최대로 얻으려고 한다. 다만, 같은 컨텐츠는 반복해서 수행될 수 없다.

예를 들어, 캐릭터가 보유하고 있는 스태미나의 양이 $100$이고 제공된 $3$개의 컨텐츠가 (스태미나 소모량, 경험치)의 형식으로 $(40,200)$, $(50, 150)$, $(30, 180)$ 와 같이 순서대로 주어져 있다고 하자. 이 상황에서 경험치를 가장 많이 얻는 방법은, $1$번과 $3$번 컨텐츠를 각각 한번씩 수행하는 것이다. 이 경우 스태미나는 $70$을 소모하고 경험치는 $380$을 얻게 된다.

캐릭터가 보유하고 있는 스태미나의 양과 컨텐츠의 개수, 그리고 각 컨텐츠마다 스태미나 소모량과 얻는 경험치가 목록으로 주어졌을 때, 캐릭터가 얻을 수 있는 경험치의 최대값을 출력하는 프로그램을 작성하라.

입력 형식

첫째 줄에 캐릭터가 보유한 스테미나의 양을 나타내는 자연수 $S$가 주어진다. ($1 \le S \le 10\,000$)

다음 줄에 제공된 컨텐츠의 개수 $N$이 주어진다. ($1 \le N \le 1\,000$)

다음 $N$개의 줄에 각 컨텐츠마다 스태미나 소모량 $U$와 얻는 경험치 $E$가 순서대로 주어진다. ($1 \le U \le 10\,000$, $1 \le E \le 100\,000$) 게임을 시작할 때, 캐릭터의 경험치는 $0$이다.

출력 형식

출력의 첫 줄에 캐릭터가 얻을 수 있는 경험치의 최대량을 출력한다. 다음 줄에 수행한 컨텐츠의 개수를 출력한다. 다음 줄에 수행한 컨텐츠의 번호를 중복없이 모두 출력한다. 컨텐츠들의 번호는 $1$이상 $N$이하이며, 컨텐츠 번호 출력 순서는 상관이 없다. 캐릭터가 얻을 수 있는 경험치의 최대량이 $0$인 경우는 없다. 답이 여러 가지인 경우 그 중 아무거나 하나 출력한다.

예제

100
3
40 200
50 150
30 180

380
2
1 3

채점 방식

입력 케이스들 각각에 대해 동일한 점수가 배분된다. 특이사항으로, 만약 경험치의 최대량을 출력하였지만 수행한 컨텐츠 정보를 출력하지 않을 경우에는 테스트케이스 마다 배분된 점수의 $50\%$를 받는다. 단, 틀린 컨텐츠 정보를 출력할 경우에는 점수를 받지 못한다.

해설