Edgar ha aconseguit arribar a la gran final del prestigiós concurs MMAPE (Millor Mestre Artesà Pastisser d'Espanya)! Després de mesos de competició intensa, ara s'enfronta al repte definitiu: impressionar un jurat exigent amb les seves creacions de pastisseria d'alta gamma.

Per preparar-se per la final, Edgar ha estat practicant i perfeccionant \(N\) \((1 \le N \le 300,000)\) receptes de pastissos diferents. Cada pastís té dues qualitats fonamentals que el jurat avaluarà:

• Sabor (\(S\)): La qualitat gustativa del pastís \((1 \le S \le 10^9)\)
• Estètica (\(E\)): La presentació i aspecte visual \((1 \le E \le 10^9)\)

El jurat està format per \(M\) \((1 \le M \le 300,000)\) membres experts, cadascun amb les seves pròpies preferències i criteris d'avaluació. Alguns membres valoren més el sabor tradicional i l'experiència en boca, mentre que d'altres són més exigents amb la presentació i l'aspecte artístic del pastís.

Per cada prova de la final, un membre diferent del jurat actuarà com a jutge principal. Cada membre del jurat té els següents pesos d'avaluació:

• Pes del Sabor (\(PS\)): Quant valora el sabor \((1 \le PS \le 10^9)\)
• Pes de l'Estètica (\(PE\)): Quant valora l'estètica \((1 \le PE \le 10^9)\)

Quan Edgar presenta el pastís al jutge, la puntuació final que rep es calcula amb la fórmula:

Puntuació = \(PS \times S + PE \times E\)

Edgar pot utilitzar qualsevol dels seus \(N\) pastissos en qualsevol prova, i fins i tot pot repetir el mateix pastís en múltiples proves si ho considera òptim. El que compta és maximitzar cada puntuació individual.

Ajuda Edgar a determinar, per cadascuna de les \(M\) proves de la final, quin és el màxim de punts que pot aconseguir triant el pastís més adequat per a cada membre del jurat.

Nota: Les puntuacions poden ser molt grans i no cabre en un enter de 32 bits amb signe.

Entrada

La primera línia d'entrada consisteix en un únic enter, \(N\).

Segueixen \(N\) línies, cadascuna amb dos enters separats per espais, \(S\) i \(E\).

La següent línia consisteix en un únic enter, \(M\).

Segueixen \(M\) línies, cadascuna amb dos enters separats per espais, \(PS\) i \(PE\).

Sortida

Escriu \(M\) línies, on cada línia conté la puntuació màxima que Edgar pot aconseguir en cada prova.

Exemple d'Entrada

2
1 10
8 2
2
10 1
1 10

Exemple de Sortida

82
101

Explicació Exemple

Edgar ha practicat 2 pastissos:

• Pastís 1: Sabor = 1, Estètica = 10 (visualment espectacular però sabor simple)
• Pastís 2: Sabor = 8, Estètica = 2 (sabor increïble però presentació bàsica)

Hi ha 2 membres del jurat:

Primera prova (Jutge 1): Aquest jutge valora molt el sabor (\(PS_1=10\)) i poc l'estètica (\(PE_1=1\))

• Si Edgar presenta el Pastís 1: \(10 \times 1 + 1 \times 10 = 20\) punts
• Si Edgar presenta el Pastís 2: \(10 \times 8 + 1 \times 2 = 82\) punts ✓

La millor opció és el Pastís 2, amb 82 punts.

Segona prova (Jutge 2): Aquest jutge és més visual, valora poc el sabor (\(PS_2=1\)) però molt l'estètica (\(PE_2=10\))

• Si Edgar presenta el Pastís 1: \(1 \times 1 + 10 \times 10 = 101\) punts ✓
• Si Edgar presenta el Pastís 2: \(1 \times 8 + 10 \times 2 = 28\) punts

La millor opció és el Pastís 1, amb 101 punts.