Ferran, un jubilat de la RENFE que està fart de donar de menjar als coloms del park ha fet un estudi per tal d’optimitzar la velocitat de l’AVE. L’estudi es basa en fer una distribució, el més acurada possible, de la massa dels passatgers que porta el tren. Partint d’una velocitat standard de 300 kms/hora, aquesta es pot veure afectada segons es situin els passatgers al llarg del tren. Si la càrrega que hi ha costat dret i esquerre no són iguals la velocitat disminueix un 2 Kms/h per casa 50 Kgs complerts També és important que la càrrega estigui ben distribuïda al llarg de tots els vagons del tren. Si la càrrega no és simètrica la velocitat disminueix un 5 Kms/h per cada 100 kgs. de diferència entre la primera meitat i la segona meitat del tren. Això que el Ferran vol dissenyar un algorisme per donar indicacions al maquinista a quina velocitat pot anar, en funció del passatgers que porti

Entrada

La primera línea es el nombre de casos de prova. Cada cas de prova, primer ens indica el nombre de fileres del tren, i a continuació una llista de pesos dels passatgers de dos columnes (una per la finestra dreta i un altre per la finestra de l’esquerra).

Sortida

Per cada cas de prova, s’ha de treure el número que indiqui la velocitat màxima a la que pot circular el tren.

Exemple d'Entrada

3
5
50 50
60 50
80 34
75 34
60 50
3
123 25
75 86
62 98
4
55 12
34 65
105 65
76 90

Exemple de Sortida

296
298
295