En el joc Dungeon Doors, hi ha una prova on els jugadors exploren una misteriosa masmorra on cada porta conté muntanyes d'or. Cada personatge té diferents habilitats de lockpicking i només pot desbloquejar certes portes. A més, el sistema del joc limita quantes portes pot obrir cada aventurer abans d'esgotar la seva destresa. Un cop un jugador utilitza la seva habilitat per obrir una porta, la porta es queda bloquejada, impedint que altres aventurers puguin accedir-hi.

L'objectiu és determinar quin dels nostres herois aconsegueix més or i es converteix en el guanyador de la prova.

Entrada

La primera línia indica el nombre de casos de prova.

Per cada cas de prova:

• La primera línia indica el nombre de jugadors J.
• La segona línia el nombre de portes que hi ha P.
• Seguidament, apareix una matriu J x P d’uns i zeros que indica si un jugador té la capacitat o no d’obrir cada porta. (1 té capacitat, 0 no en té). La primera fila fa referència al primer jugador, la següent al segon…, fins al darrer.
• Després apareix una línia de P nombres que fa que els jugadors sàpiguen el valor en or de cada porta, d’aquesta forma sempre escolliran les portes que sumin més or.
• Finalment, un nombre L que indica les portes que pot obrir cada aventurer.

Els jugadors accedeixen a la masmorra del primer al darrer, no hi ha canvis d’ordre. Es garanteix que P >= L

Sortida

Per cada cas de prova, cal mostrar quin jugador ha aconseguit més or (el primer, el segon…) indicant el número i la quantitat d’or aconseguit. Si hi ha empat, es mostrarà el jugador que vagi abans en ordre. Es garanteix que com a mínim un jugador tindrà un valor major a 0 d’or.

Exemple d'Entrada

2
2
4
1 1 0 0
0 1 1 1
10 20 30 40
2
3
6
1 0 1 0 1 1
0 1 0 1 0 1
1 1 0 1 1 1
10 20 30 40 50 60
3

Exemple de Sortida

2 70
1 140