가방 하나와 N개의 물건이 주어집니다. 가방의 용량 W(>0)와 각 물건의 가치 v(>0)와 크기 w(>0)가 주어집니다. N개의 물건 중 어떤 물건으로 가방을 채워야 가장 이득이 클까요? 물건은 포함하고나 포함하지 않을 수 있습니다. 즉, 물건의 일부만 포함할 수 없습니다.

첫 줄에는 테스트케이스 T(1<=T<=1,000)가 주어집니다. 각 테스트케이스마다 첫 줄에는 가방의 용량 W(1<=W<=100)와 물건의 개수 N(1<=N<=500)이 주어집니다. 그다음 줄에는 N개의 물건에 대해 그것의 가치 v(1<=v<=50)와 크기 w(1<=w<=100)가 주어집니다. 첫 물건부터 차례로 0부터 번호를 할당합니다.

각 테스트케이스마다 주어진 물건으로 가방을 채웠을 때 얻을 수 있는 가장 큰 이득을 출력해 주세요.