Estás jugando por enésima vez a tu juego favorito, Sótanos y criaturas parecidas a las palomas. Usted conoces el juego bastante bien, pero nunca le has dedicado el tiempo suficiente para averiguar la mejor estrategia.

Es decir, hasta ahora. El juego consiste en una determinada secuencia de eventos, como luchar contra un monstruo o salvar a un gato de un árbol, y tienes que completar todos los eventos para ganar. A cada evento se le asigna un atributo, como la fuerza, y un umbral, un número entero positivo. Si la puntuación de tus atributos coincide con el umbral o lo supera, habrás completado la prueba con éxito. Si no es así, desgraciadamente se acabó el juego y tu puntuación total será cero.

Si completas todos los eventos con éxito, tu puntuación depende de lo bien que lo hayas hecho durante estos eventos. Si tu puntuación de atributos coincide exactamente con el umbral de un evento, obtienes ~0~ puntos, pasando apenas por ese evento. Si superas el umbral, obtienes puntos iguales a tu puntuación de atributos que se utilizó para ese evento.

Tarea

Ahora estás en la parte final del juego, pero primero tienes que gastar algunos puntos de atributos para aumentar tu puntuación de atributos. Ya sabes qué eventos ocurrirán durante la parte final del juego, así que lo único que queda es averiguar qué atributos aumentar.

Entrada

La entrada consiste en:

• Una línea que contiene un número entero ~n~ ~(1 \le n \le 10^5)~ y un número entero ~k~ ~(1 \le k \le 10^9)~, el número de atributos y el número de puntos de atributo que aún puede gastar.
• ~n~ líneas, cada una de las cuales contiene un nombre de atributo distinto, y un entero ~s~ ~(0 \le s \le 10^9)~, la puntuación actual que tienes en ese atributo.
• Una línea que contiene un entero ~l~ ~(1 \le l \le 10^5)~, el número de eventos.
• ~l~ líneas que describen cada uno de los eventos, que contienen el nombre del atributo que se utiliza, y un número entero ~t~ ~(0 \le t \le 10^9)~, el umbral de este evento. Los nombres de los atributos constan de letras mayúsculas del alfabelo inglés ~(A-Z)~, y tienen una longitud entre ~1~ y ~20~ caracteres inclusive.

Salida

Da salida a la puntuación máxima que se puede obtener de los eventos.

Ejemplo #1 de Entrada

2 3
STR 15
CON 12
2
STR 17
CON 14

Ejemplo #1 de Salida

0

Ejemplo #2 de Entrada

3 7
JUMP 5
RUN 7
FLY 0
4
FLY 0
JUMP 6
RUN 10
RUN 8

Ejemplo #2 de Salida

31