사탕

당신은 사탕 공장의 주인이다. 날마다 사탕 $J$개를 상자에 담아 가게로 보내야 한다.

공장에는 상자가 $N$개 있고, 크기는 서로 다를 수 있다. 상자는 되도록 적게 쓰려고 한다. 상자를 가득 채울 필요는 없고, 일부만 채워도 된다.

사탕의 개수와 각 상자의 크기를 입력받아, 사탕을 모두 담는 데 필요한 상자의 최소 개수를 출력하는 프로그램을 작성하라. 사탕을 모두 담을 공간은 충분하다고 보장한다.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다. 각 테스트 케이스는 아래 형식을 따른다.

테스트 케이스의 첫 줄에 사탕의 개수 $J$와 상자의 개수 $N$이 주어진다 ($1 \le J, N \le 1000$).

다음 $N$개의 줄에는 줄마다 $i$번째 상자의 세로 길이 $R_i$와 가로 길이 $C_i$가 주어진다 ($1 \le R_i, C_i \le 10000$). 두 상자의 크기가 같을 수도 있다. 한 상자에는 사탕을 $R_i \times C_i$개보다 많이 담을 수 없다.

$T$개의 줄을 출력한다. 각 줄에 $i$번째 테스트 케이스에서 필요한 상자의 최소 개수를 출력한다.