Benzina

Ia uite, frate! E numărul meu norocos cu săgeată!

În anul $1938$, pe faimoasa Route $66$ din America se aflau $N$ benzinării. Route $66$ începe din Chicago și se termină în Los Angeles, conectând cele $2$ metropole americane. Benzinăriile sunt descrise prin borna de mile în dreptul căreia sunt, așa că benzinăria de pe poziția $i$ se află la mila $D_i$ față de punctul de start, Chicago.

În ziua de $4$ iulie $1938$, o mulțime de familii americane se întorc din Los Angeles (locul unde lucrează toți americanii din $1938$) pe Route $66$, pentru a petrece Ziua Independenței cu familiile lor din Chicago (locul unde locuiesc toți americanii din $1938$). Fiecare mașină este caracterizată de benzinăria în dreptul căreia se află în momentul de față. Toate familiile au o sumă de $K$ dolari. Guvernul taxează fiecare milă deplasată cu $1$ dolar și fiecare benzinărie pe lângă care trece o mașină cu $C$ dolari. Așa că, dacă o mașină este în dreptul benzinăriei $i$ și vrea să se oprească la benzinăria $j$, cu $j < i$ (mașinile merg doar înspre Chicago, nu se întorc), atunci costul plătit de o familie este $D_i - D_j + C \cdot (i - j)$. Așadar, o familie poate ajunge la o anumită benzinărie doar dacă suma de $K$ dolari poate acoperi costul drumului.

Cerință

Franklin D. Roosevelt (președintele S.U.A. din $1938$) vă cere să calculați următoarele valori pentru a înțelege mai bine viața unui simplu american:

1. Cea mai apropiată benzinărie de Chicago la care poate ajunge o mașină aflată inițial la benzinăria $i$, pentru fiecare benzinărie din cele $N$.
2. Numărul maxim de mașini care pot alimenta cu benzină dacă, în fiecare benzinărie, poate alimenta maximum o mașină. Pentru ca o mașină să alimenteze în benzinăria $i$ trebuie să iși permită să ajungă până la aceasta (o mașină poate alimenta la o benzinărie dacă suma ei rămasă de bani după plătirea drumului este $\geq 0$).

Date de intrare

Pe prima linie a fișierului de intrare benzina.in se găsește $T$, cerința care trebuie rezolvată.
Pe a doua linie se găsesc trei numere naturale: $N, C, K$, reprezentând numărul de benzinării, taxa pentru trecerea pe lângă o benzinărie și suma de dolari pe care o deține fiecare familie.
Pe a treia linie se găsesc $N$ numere naturale: $D_1, D_2, ..., D_N$, reprezentând distanțele la care se află cele $N$ benzinării față de Chicago.
Pe a patra linie se găsesc $N$ numere naturale: $Nr_1, Nr_2, ..., Nr_N$, reprezentând numărul de mașini care se află în dreptul fiecărei benzinării.

Date de ieșire

• Dacă $T = 1$, atunci pe prima linie a fișierului de ieșire benzina.out se vor găsi $N$ numere naturale $S_1, S_2, ..., S_N$, unde $S_i$ reprezintă cea mai apropiată benzinărie de Chicago la care poate ajunge o mașină aflată inițial la benzinăria $i$.
• Dacă $T = 2$, atunci pe prima linie a fișierului de ieșire benzina.out se va găsi un singur număr natural $M$, reprezentând numărul maxim de mașini care pot alimenta cu benzină.

Restricții și precizări

• $T \in \{ 1, 2 \}$;
• $1 \leq N \leq 200 \ 000$;
• $0 \leq C, K \leq 10^9$;
• $0 \leq D_i \leq 10^9$;
• $0 \leq Nr_i \leq 10^9$;
• $D_{i - 1} \leq D_i$, pentru $2 \leq i \leq N$;

  #	Punctaj	Restricții
  1	13	$T = 1$ și $N \leq 1000$
  2	28	$T = 1$
  3	7	$T = 2$ și $Nr_i \leq 1$
  4	29	$T = 2$ și $N \leq 1000$
  5	23	$T = 2$

Exemplul 1

benzina.in

1
4 2 5
1 3 5 8
2 0 1 0

benzina.out

1 1 2 3

Explicație

$T = 1$, deci trebuie să rezolvăm cerința $1$. Sunt $N = 4$ benzinării, taxa guvernului pentru fiecare benzinărie depășită este $C = 2$ și suma de dolari a fiecărei familii este $K = 5$.

• O mașină aflată la benzinăria $1$ poate ajunge la benzinăria $1$.
• O mașină aflată la benzinăria $2$ poate ajunge la benzinăria $1$.
• O mașină aflată la benzinăria $3$ poate ajunge la benzinăria $2$.
• O mașină aflată la benzinăria $4$ poate ajunge la benzinăria $3$.

Exemplul 2

benzina.in

2
4 2 5
1 3 5 8
2 0 1 0

benzina.out

2

Explicație

$T = 2$, deci trebuie să rezolvăm cerința $2$. Numărul maxim de mașini care pot fi alimentate este $M = 2$. O soluție cu acest număr maxim este următoarea:

• Prima mașină de la benzinăria $1$ alimentează la benzinăria $1$.
• A doua mașină de la benzinăria $1$ nu alimentează.
• Mașina de la benzinăria $3$ alimentează la benzinăria $3$.

Se poate demonstra că numărul maxim de mașini care pot alimenta în acest caz este $2$.