개의 오렌지가 있다. 번째 오렌지의 무게 점수는 , 맛 점수는 이다.
두 사람이 모든 오렌지를 나누어 구매한다. 첫 번째 사람은 정확히 개의 오렌지를 고르고, 두 번째 사람은 나머지 오렌지를 모두 구매한다.
두 사람의 만족도는 첫 번째 사람이 구매한 오렌지들의 무게 점수의 합과 두 번째 사람이 구매한 오렌지들의 맛 점수의 합을 더한 값이다.
만족도의 최댓값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 만족도의 최댓값을 한 줄에 출력한다.
첫째 줄의 는 테스트 케이스의 수이다. 각 케이스는 다음과 같은 형식으로 주어진다.
