인터넷 서점

문제 정보

문제

새 학기가 시작되면 항상 부담되는 것이 비싼 교과서 가격이다. 오랜 병특 생활을 마치고 복학한 스탱은 이번 학기에 사야 하는 N 권의 교과서를 인터넷 서점에서 사기로 했다. 인터넷 서점 간의 과다 경쟁으로 인해 모든 서점들은 한 권을 사더라도 무료 배송을 실시하고 있으며, 교내 서점보다 가격도 저렴하다.

그런데, 스탱은 자신이 가입해 있는 M 군데의 인터넷 서점마다 각각의 교과서 가격이 다르다는 것을 발견하게 되었다. 단순하게 한 서점이 다른 서점보다 항상 싸거나 항상 비싼 경우라면 간단하겠지만, 실제로는 교과서마다 가장 싸게 파는 서점이 서로 달랐다. 각 교과서마다 가장 싸게 파는 서점에 가서 사면 좋겠지만, 한 서점에서 책을 많이 사면 회원등급이 오르는 혜택이 있기 때문에 스탱은 서점 하나를 골라 책 전부를 구입하기로 결정했다.

문제는, 각 서점들은 포인트 제도를 실시한다는 것이다. 각 서점에서 책을 사면 책 값의 일부에 해당하는 포인트가 적립되는데, 이 포인트는 다른 책을 살 때 책값의 전부 혹은 일부를 내는 데 사용할 수 있다. 따라서, 어느 순서로 책을 구매하느냐에 따라서 결과적으로 스탱이 쓰는 돈이 달라질 수 있다.

스탱은 이와 같은 상황 하에서, 어느 서점에서 책을 사야 가장 돈을 적게 쓸 수 있을지를 알고 싶어 한다. 스탱에게는 남아 있는 포인트가 하나도 없으며, 책을 모두 구입한 뒤 남는 포인트에는 신경을 쓰지 않는다고 가정하자.

예를 들어, 다음은 스탱이 구입해야 할 교과서들의 목록과 3군데의 인터넷 서점에서의 가격 및 적립 포인트의 한 예를 보여준다.

교과서서점 
No24 뵤고문고40인의 도적
가격포인트가격포인트가격포인트
알고스팟 저지 7일만에 만들기5,000 500 6,000 1,200 5,500 550
동적 계획법 30분만에 마스터3,000 300 3,000 1,000 3,500 350
10년에 마스터하는 파이썬1,500 0 2,000 500 5,500 550
검색 엔진 for dummies 5,000 500 5,500 1,500 2,000 100

이 경우에는 전반적으로 No24 가 저렴하지만, 포인트는 뵤고문고가 훨씬 많이 적립을 해 준다는 것을 알 수 있다. 실제로 No24 에서 책을 구입하게 되면 13,200원이 들지만, 뵤고문고에서 구입하면 12,800원이면 충분하다. 어떤 서점에서 책을 구입해야 가장 적은 돈을 쓰게 되는지를 계산하는 프로그램을 작성하라.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어진다. 각 테스트 케이스의 첫 줄에는 스탱이 사야 하는 책의 수 N (1 <= N <= 200) 과 서점의 수 M (1 <= M <= 100) 이 주어지며, 그 후 N 줄에 각각 M 개의 정수 쌍이 주어진다. 이 때 i 번째 줄의 j 번째 쌍은 i 번째 책이 j 번째 서점에서 팔리는 가격과 적립 포인트를 순서대로 나타낸다.

모든 책의 가격은 10,000 이하의 자연수이며, 적립 포인트는 책의 가격보다 작은 음이 아닌 정수이다.

출력

각 테스트 케이스마다 한 줄로, 스탱이 써야 하는 최소의 금액을 출력한다.

예제 입력

1 
4 3
5000 500 6000 1200 5500 550 
3000 300 3000 1000 3500 350 
1500 0 2000 500 5500 550 
5000 500 5500 1500 2000 100

예제 출력

12800

노트

20개의 댓글이 있습니다.