소프트웨어 회사

한 소프트웨어 개발 회사가 두 개의 프로그래밍 프로젝트를 맡았다. 두 프로젝트는 같은 계약에 묶여 있어 반드시 동시에 납품해야 한다. 한쪽을 먼저 끝내도 아무런 도움이 되지 않는다.

이 회사에는 작업을 수행할 직원이 $n$명 있다. 두 프로젝트를 더 쉽게 관리하기 위해, 각 프로젝트는 서로 독립적인 $m$개의 하위 작업(subproject)으로 나뉘어 있다. 하나의 하위 작업은 한 번에 한 명의 직원만 수행할 수 있지만, 서로 다른 하위 작업이라면 여러 직원이 같은 프로젝트의 하위 작업들을 동시에 진행할 수 있다.

한 직원은 여러 개의 하위 작업을 맡아 순차적으로 처리할 수 있으며, 그 직원의 작업 시간은 맡은 하위 작업들의 소요 시간의 합이다. 목표는 두 프로젝트를 가능한 한 빨리 끝내는 것, 즉 모든 하위 작업이 완료되는 시각(직원들 중 가장 큰 총 작업 시간)을 최소화하는 것이다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 11$)가 주어진다. 이후 각 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$ ($1 \le n \le 100$)과 $m$ ($1 \le m \le 100$)이 주어진다. 이어서 $n$개의 줄이 주어지며, $i$번째 줄에는 두 정수 $x_i$와 $y_i$가 주어진다. $x_i$는 $i$번 직원이 첫 번째 프로젝트의 하위 작업 하나를 끝내는 데 걸리는 시간(초)이고, $y_i$는 두 번째 프로젝트의 하위 작업 하나를 끝내는 데 걸리는 시간(초)이다.

각 테스트 케이스마다 한 줄에, 두 프로젝트를 모두 완료할 수 있는 최소 시간(초)을 정수로 출력한다.