Universal Cup Judging System

Universal Cup

Límite de tiempo: 1 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Tú y tus dos compañeros de equipo están participando en un concurso de programación, pero debido a los exámenes finales, todos tienen que irse temprano. Cada uno de ustedes tiene un tiempo de salida específico $\ell_i$ (el tiempo en minutos después de que comienza el concurso en el que debes irte). Después del concurso, revisan las soluciones y se dan cuenta de que cada problema se adapta perfectamente a uno de ustedes: el problema $i$ lo resuelve mejor la persona $p_i$, quien puede completarlo en $c_i$ minutos sin ningún envío incorrecto. Desafortunadamente, debido a la presión de los exámenes, no tuvieron un buen desempeño en el concurso original.

En un sueño, ves al equipo campeón en la transmisión en vivo: resolvieron todos los $n$ problemas con un tiempo de penalización total $t$. Cuando despiertas, descubres que has renacido en la mañana del día del concurso. Ahora, con un recuerdo perfecto de todos los detalles de los problemas y del desempeño del campeón, quieres determinar si hay alguna manera de vencerlos esta vez.

Las reglas del concurso establecen:

  • Solo hay una computadora disponible, por lo que los problemas deben resolverse secuencialmente (uno tras otro).
  • Cada problema $i$ debe asignarse a la persona $p_i$, quien debe comenzar a resolverlo antes de su tiempo de salida $\ell_{p_i}$.
  • Si la persona $p_i$ comienza a resolver el problema $i$ en el tiempo $s$, debe terminar cumpliendo $s + c_i \le \ell_{p_i}$.
  • El tiempo de penalización total es la suma de los tiempos de finalización de todos los problemas resueltos.

Dados $n$, $t$, y los parámetros $p_i$ y $c_i$ para cada problema, determina si existe un orden para resolver los problemas tal que:

  • Se resuelvan todos los $n$ problemas.
  • El tiempo de penalización total sea estrictamente menor que $t$.

Si existe tal disposición, imprime YES; de lo contrario, imprime NO.

Entrada

La primera línea contiene un solo entero $q$ ($1 \le q \le 10^5$), el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene cuatro enteros: $n$, $\ell_1$, $\ell_2$ y $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), que representan el número de problemas y los tiempos de salida (en minutos después del inicio del concurso) de los tres compañeros de equipo.

Cada una de las siguientes $n$ líneas contiene dos enteros, $p_i$ y $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), donde $p_i$ denota el compañero designado para el problema $i$, y $c_i$ es el tiempo requerido (en minutos) para que lo complete.

La última línea contiene un solo entero $t$ ($1 \le t \le 10^{13}$), que representa el tiempo de penalización total del equipo campeón.

La suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, si existe un orden de resolución de problemas que satisfaga las restricciones (todos los problemas resueltos y penalización estrictamente menor que $t$), imprime YES; de lo contrario, imprime NO.

Ejemplos

2
3 100 150 175
1 100
2 25
3 50
401
5 100 200 300
1 30
1 30
1 40
2 110
3 50
1275
YES
NO
1
1 100 300 300
1 300
300
NO

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.