Hate màxim P28087

Enguany entre els equips de la UPC hi ha hagut molt flux de “hate”, perquè hi havia un emissor de hate tremendo, en Baq, i un magnífic receptor de hate, en Pesao. Totes les altres persones, més “normals”, només feien de transmissors del hate que rebien. Considereu el model simplificat següent:

En Baq podia emetre com a molt B_i unitats de hate a la persona i-èsima. Sorprenentment, ningú odiava en Baq. En Pesao, en canvi, només feia que rebre hate. D’altra banda, cada persona normal i reenviava tot el hate que rebia a una altra persona h_i. Addicionalment, cada persona normal i tenia un límit ℓ_i de hate que podia rebre abans de posar-se a plorar i no voler menjar mai més kebabs amb ningú.

En Baq va aconseguir fer arribar el màxim hate possible al Pesao sense que ningú deixés de fer kebabs amb ell. Quin és aquest nombre d’unitats de hate?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un enter n, indicant que als equips UPC hi ha n+2 persones, numerades entre 0 i n+1. En Pesao és el 0, en Baq és el n+1, i les n persones normals tenen nombres entre 1 i n.

Segueixen n línies, una per a cada persona normal, cadascuna amb h_i i ℓ_i. Finalment ve una línia amb n+1 enters, que són els B_i en ordre. Suposeu 0 ≤ n ≤ 10⁵, 0 ≤ h_i ≤ n, que tots els ℓ_i i B_i estan entre 0 i 10¹⁰, i que el graf de transmissió de hate no té cap cicle.

Sortida

Per a cada cas, escriviu el hate que en Baq va poder fer arribar al Pesao.