BMX


Submit solution

Points: 40 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Le BMX freestyle est une discipline (passionnante) du BMX qui peut être paratiquée dans les rues, parcs ou sur piste. Le pricipe est de réaliser avec un vélo BMX des acrobaties qu'on appelle des figures. Daniel Dhers est l'un des meilleurs riders BMX, il a emporté les plus grandes compétitions du bmx freestyle.

Aujourd'hui Daniel Dhers participe au FISE, la plus grande compétition de sport freestyle. Il est le dernier rider à jouer. On se donne l'objectif de savoir si Daniel pourra gagner la première place.

Daniel Dhers maitrise un certain nombre de figures, ce dernier connait à priori le nombre de points que chaque figure va lui apporter ainsi que le temps nécessaire pour la réaliser. Le score total d'une performance est égal à la somme des points des figures réalisées plus le nombre des différentes figures réalisées.

\(\text{Score total} = \sum (\text{points des figures réalisées}) + \text{ nombre des différentes figures réalisées}\)

Input Specification

La première ligne de l'entrée contient un entier \( 1\leq T \leq 100\), désignant le nombre de cas tests.

Chaque cas test commence par une ligne qui contient un entier \(1 \leq N \leq 10000\) le nombre de joueurs qui sont passés avant Daniel. Suivie d'une autre ligne avec \(N\) entiers \(H_i\) (\( 0 \leq H_i \leq 100000 \)) séparés par des espaces, donnant le nombre de points que le joueur \(i\) a remporté.

Ensuite, une ligne avec deux entiers \(1 \leq M \leq 100\) et \(1 \leq S \leq 1000\) va suivre, donnant respectivement le nombre de figures que Daniel maîtrise et le temps qui lui est alloué pour réaliser sa performance. Après cela vont suivre \(M\) lignes constituées de deux entiers \(P_i\) et \(X_i\) (\(1 \leq P_i \leq 100000\) et \(1 \leq X_i \leq S\)) chacune, qui donnent respectivement le nombre de points que la figure \(i\) va apporter au joueur et le temps nécessaire pour la réaliser.

Output Specification

Pour chaque cas test, afficher le nombre de points max que Daniel Dhers peut remporter suivi par "Yes" si ce nombre de points lui permettra de gagner la première place ou "No" sinon.

Scoring

\begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 5 & M = 1 \cr \hline 2 & 10 & \text{Pour chaque figure \(Xi\) = 1} \cr \hline 3 & 10 & \text{Pour chaque figure \(Pi\) = 1} \cr \hline 4 & 20 & M \leq 20 \cr \hline 5 & 55 & \text{Pas de contraintes supplémentaires} \cr \hline \end{array}

Sample Input

1
4
10 20 35 15
5 9
5 2
5 2
8 2
10 3
2 3

Sample Output

36 Yes

Notes

Notez que Daniel pourra bien répéter une figure plusieurs fois.


Comments

There are no comments at the moment.