#2534 Midnight meal

2 s   64 MB  

Description

기숙사에 살고 있던 A군과 B군은 야식 매니아이다. 야식을 자주 먹지만 항상 어떤 야식을 먹어야 할 지 고민을 하고 있다. 1주일 넘게 고민을 하던 A군이 B군에게 다음과 같이 제안하였다.

“야식 목록을 써놓고 점수를 매겨서 제일 높은 점수를 받은 야식을 주문하도록 하자!”

별다른 대안이 없었던 B군은 A군의 제안에 동의하였다. 그러나 덧셈에 미숙한 A군과 B군은 서로의 점수를 써 놓은 종이를 가지고도 어떤 야식을 주문해야 하는지 알지 못했다. 당신을 불쌍한 A군과 B군을 위해 어떤 야식을 주문해야 하는지 알려주는 프로그램을 작성하여야 한다.

Input

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스 수 T (1≤T≤20) 가 주어진다. 각 테스트 케이스의 첫 줄에는 야식의 종류 N이 주어지고, 그 다음 N줄에 야식 이름, A군이 매긴 점수, B군이 매긴 점수가 공백 하나를 사이에 두고 입력된다. 야식의 종류는 최대 50가지이다. 야식 이름은 알파벳 소문자로 이루어져 있고 50글자를 넘지 않는다. A군이 매긴 점수와 B군이 매긴 점수의 합은 각각 다르다. (즉, 제일 높은 점수를 받은 야식은 언제나 한 가지이다.)

Output

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 최고 점수를 받은 야식을 출력한다.

Sample Input

Sample Output

3
3
pizza 4 1
chicken 10 2
noodle 1 5
3
soju 1 1
beer 1 4
whiskey 1 2
1
donburi 3 2
chicken
beer
donburi

Source

KPC'07 - Contest session