Avtomagistral#3038

Avtomagistral

1 saniyə

256 meqabayt

Çətin

Olimpiya şəhərinin Loqarifmik bölgəsindən olan komanda, uzaq Eksponensialsk şəhərində keçiriləcək Olimpiadaya hazırlaşır. Komanda ora öz avtobusları ilə gedəcək. Loqarifmik bölgəni Eksponensialsk şəhəri ilə birləşdirən avtomagistral ardıcıl $N$ hissədən ibarətdir. Hər hissədə komanda ya pulsuz yolu seçə bilər, bu yol $a_{i}$ a_i saniyə çəkir, ya da ödənişli yolu seçə bilər, bu halda $c_{i}$ c_i Olimpiya senti ödəməli və yol $b_{i}$ b_i saniyə çəkəcəkdir. Seqmentlərin arasında istənilən istiqamətdə yol növünü dəyişməyə imkan verən körpülər var və bu dəyişmə üçün hər dəfə $q_{i}$ q_i saniyə vaxt sərf olunur. Eyni növ yolda davam etmək isə əlavə vaxt tələb etmir. Səfərin başlanğıcında istənilən yol növündən başlamağa və son seqmenti istənilən yol növündə bitirməyə icazə verilir. Körpülər yalnız $1$ -ci və $2$ -ci, $2$ -ci və $3$ -cü, ..., $(N - 1)$ (N-1)-ci və $N$ -ci seqmentlər arasında var.

Olimpiadaya səfər zamanı vaxtında çatmaq olduqca vacibdir, ona görə komanda ən gec $T$ saniyədə Loqarifmik bölgəsindən Eksponensialsk şəhərinə getmək üçün tələb olunan minimal ödənişi öyrənmək istəyir. Geri dönüşdə isə vaxt vacib deyil və komanda ödənişlərə $S$ sentdən artıq pul verməmək şərti ilə mümkün olan minimal vaxtla dönmək istəyir. Bütün yol vaxtları və ödənişləri hər iki istiqamətdə eynidir.

Verilmiş yol haqqında məlumat əsasında aşağıdakılarnı tapacaq proqram yazın:

Olimpiadaya mümkün olan $T$ saniyə müddətində çatmaq üçün tələb olunan minimal ödəniş;
Olimpiadadan geri dönüşdə ödənişlər $S$ sentdən çox olmayan halda ən qısa müddət.

Giriş

Birinci sətirdə üç tam ədəd: $N$ ( $2 \leq N \leq 40$ 2 \le N \le 40) — avtomagistral seqmentlərinin sayı, $T$ ( $0 \leq T \leq 1 0^{16}$ 0 \le T \le 10^{16}) — birinci hissə üçün vaxt limiti, və $S$ ( $0 \leq S \leq 1 0^{16}$ 0 \le S \le 10^{16}) — ikinci hissə üçün ödəniş limiti. İkinci sətirdə üç tam ədəd $a_{1}$ a_1, $b_{1}$ b_1, və $c_{1}$ c_1 — birinci seqmentin pulsuz və ödənişli yollarında hərəkət müddəti, və ödənişli yoldakı ödəniş. Növbəti $N - 1$ N-1 sətirdə dörd tam ədəd $q_{i}$ q_i, $a_{i}$ a_i, $b_{i}$ b_i, və $c_{i}$ c_i verilir — yol növünün dəyişməsi üçün vaxt, sonra həmin seqmentdə pulsuz və ödənişli yolun hərəkət müddətləri və ödənişli yol üçün ödəniş. Gediş zamanı $q_{i}$ q_i $(i - 1)$ (i-1)-ci seqmentdən $i$ -ci seqmentə keçiddə yol tipini dəyişmək üçün sərf olunan vaxtdır, qayıdış zamanı isə $q_{i}$ q_i $i$ -ci seqmentdən $(i - 1)$ (i-1)-ci seqmentə keçiddə yol tipinin dəyişdirilməsinə sərf olunan vaxtdır (əgər avtobus pulsuzdan ödənişli yola və ya əksinə keçir). Bütün $a_{i}$ a_i, $b_{i}$ b_i, və $c_{i}$ c_i ( $1 \leq i \leq N$ 1 \le i \le N) $1$ -dən $1 0^{15}$ 10^{15}-ə qədər olan tam ədədlərdir. Bütün $q_{i}$ q_i ( $2 \leq i \leq N$ 2 \le i \le N) $0$ -dan $1 0^{9}$ 10^9-a qədər olan tam ədədlərdir.

Çıxış

Bir sətirdə iki tam ədəd çıxarın: Olimpiadaya $T$ saniyə ərzində çatmaq üçün tələb olunan minimal ödəniş və Olimpiadadan qayıdışda $S$ sentdən çox ödəniş etməmək şərti ilə mümkün olan minimal vaxt. Əgər uyğun yol yoxdursa, həmin hədd üçün $- 1$ çap edin.

Nümunələr

Nümunə 1

Qeyd

İzah: $2012$ saniyə məhdudiyyətində ən ucuz yol birinci seqmenti ödənişli yolla, sonra isə pulsuz yolla keçməkdir: ümumi xərc $10000 + 0 + 0 + 0 + 0 = 10000$ 10000 + 0 + 0 + 0 + 0 = 10000, vaxtı isə $17 + 4$ 17 + 4 (dəyişmə) $+ 1000 + 100 + 10 + 1 = 1132$ + 1000 + 100 + 10 + 1 = 1132-dir. Geri qayıdışda $2012$ sent xərc ilə mümkün olan ən tez yol $5$ və $4$ -cü seqmentlər pulsuz, $3$ və $2$ -ci seqmentlər ödənişli, $1$ -ci seqment pulsuz: vaxt $1 + 10 + 2$ 1 + 10 + 2 (dəyişmə) $+ 17 + 17 + 4$ + 17 + 17 + 4 (dəyişmə) $+ 10000 = 10051$ + 10000 = 10051, ödəniş $0 + 1000 + 100 + 0 + 0 = 1100$ 0 + 1000 + 100 + 0 + 0 = 1100.