Tú, el héroe, vas a luchar contra el jefe final del mundo, Irisu. Como héroe, tienes tres “habilidades” de personaje: Cuerpo $B$, Mente $M$ e Inteligencia $I$. La fuerza global $S$ se calcula como la media geométrica de estas habilidades. En otras palabras, $S=\sqrt[3]{BMI}$. Por desgracia, como perdiste la última batalla contra el jefe, todas tus habilidades valen ahora cero.

Para vencer a Irisu, tu fuerza global debe satisfacer la misteriosa desigualdad $(S+5)(S+1)(S+4)\ge X$ escrita en el pergamino ancestral que encontraste dentro de un enorme tomate después de la última batalla. La única manera de aumentar las habilidades es comprar pociones de habilidad al alquimista oscuro Skyly. Skyly vende $N_B+N_M+N_I$ pociones. Las primeras $N_B$ son pociones de Cuerpo, las siguientes $N_M$ son pociones de Mente y las últimas $N_I$ son pociones de Inteligencia. La poción número $i$ cuesta $P_i$ dólares y aumenta la habilidad correspondiente en $E_i$ puntos.

Para salvar tanto el mundo como tu bolsillo, quieres encontrar el precio total mínimo que necesitas gastar en pociones de habilidad para vencer al jefe final.

Entrada

La primera línea contiene cuatro enteros $X,N_B,N_M,N_I$, y la línea número $i$ de las siguientes $N_B+N_M+N_I$ líneas contiene dos enteros $P_i,E_i$.

• $0\le X\le10^9$
• $0\le N_B,N_M,N_I\le30$
• $0\le P_i,E_i\le10^9$ para todo $1\le i\le N_B+N_M+N_I$.

Salida

Imprime el precio total mínimo que necesitas gastar en pociones de habilidad para vencer al jefe final. Si todavía no eres lo suficientemente fuerte incluso después de comprar todas las pociones de Skyly, imprime DEAREST DROP.

Ejemplos

Entrada 1

31 4 1 5
9 2
6 5
3 5
8 9
7 9
3 2
3 8
4 6
2 6
4 3

Salida 1

12

Entrada 2

5566 2 1 0
0 999999999
999999999 0
0 0

Salida 2

DEAREST DROP

Entrada 3

50216 2 2 2
1 20
1 30
10 42
20 43
15 18
17 19

Salida 3

29