Fənərlər

Fermer Con, inək sürüsünü Alp dağlarında gəzintiyə çıxardı! Bir müddət sonra hava qaraldı və gəzinti sona çatdı. Lakin bəzi inəklər dağ silsiləsinin müxtəlif yerlərində tələyə düşdü və Con onların hamısını xilas etməyə hazırlaşır!

İnəklərin keçdiyi dağ silsiləsi 2D müstəvisində $n$ nöqtədən ibarət bir sıra kimi təsvir edilə bilər. Bu nöqtələrə "zirvələr" deyəcəyik. Zirvələr 1-dən $n$-ə qədər nömrələnib və bu ardıcıllıqla düzülüb. Zirvə $i$ koordinatlara malikdir (i, h_i). Burada h_i zirvə $i$-nin hündürlüyünü göstərir. h_1,h_2,\ldots,h_n dəyərləri 1-dən $n$-ə qədər olan ədədlərin ardıcıllığını təşkil edir. (Bu o deməkdir ki, hər bir j = 1, ..., n üçün h_i = j yalnız bir i \in \{1,...,n\} üçün mövcuddur.)

Hər bir $i$ (1\le i < n) üçün zirvələr $i$ və i+1 bir düz xətt parçası ilə birləşdirilib.

Artıq gecə olduğu üçün Con dağın hər hansı bir hissəsinə yalnız işlək bir fənər ilə gedə bilər. Xoşbəxtlikdən, satın almaq üçün $k$ fənər mövcuddur. Hər bir $j$ (1 \le j \le k) üçün, $j$-ci fənər p_j zirvəsində c_j frank qarşılığında alına bilər.

Təəssüf ki, $j$-ci fənər yalnız Con [a_j,b_j] hündürlük aralığında olduqda işləyə bilər. Başqa sözlə, cari hündürlük a_j-dən kiçik və ya b_j-dən böyük olduqda, $j$-ci fənər işləmir. Qeyd edək ki, fənərlər hündürlük aralığından çıxdıqda xarab olmur. Məsələn, Conun hündürlüyü b_j-dən çox olduqda, $j$-ci fənər işləmir, lakin Con b_j hündürlüyünə qayıtdıqda fənər yenidən işləməyə başlayır.

Əgər Con hazırda $p$ zirvəsindədirsə, o, aşağıdakı üç əməliyyatdan birini yerinə yetirə bilər:

• O, $p$ zirvəsində mövcud olan fənərlərdən birini ala bilər. Fənəri aldıqdan sonra, o, onu həmişə istifadə edə bilər.

• Əgər p > 1-dirsə, p-1 zirvəsinə keçə bilər.

• Əgər p < n-dirsə, p+1 zirvəsinə keçə bilər.

Con heç vaxt işlək fənər olmadan hərəkət etməməlidir. O, yalnız yolunun hər anında aldığı və işləyən ən azı bir fənər olduqda iki zirvə arasında keçə bilər. (Bu, bütün yol boyunca eyni fənər olmalı deyil).

Məsələn, təsəvvür edək ki, Fermer Con hazırda $4$ hündürlüyündə bir zirvədədir və hündürlüyü $1$ olan qonşu zirvəyə keçmək istəyir. Əgər Con $[1,3]$ və $[3,4]$ hündürlük aralığında işləyən fənərlərə malikdirsə, o, bir zirvədən digərinə keçə bilər.

Lakin, əgər Con $[1,1]$ və $[2,5]$ hündürlük aralığında işləyən fənərlərə malikdirsə, o, bu iki zirvə arasında keçə bilməz: çünki heç bir fənər $1.47$ hündürlüyündə işləməyəcək.

Sizin vəzifəniz müxtəlif bir-birindən asılı olmayan sorğular üçün cavabı müəyyən etməkdir.

Hər bir 1 \le j \le k üçün, a_j \le h_{p_j} \le b_j şərtini ödəyən, təsəvvür edin ki, Con $j$-ci fənəri alaraq p_j zirvəsindən səyahətinə başlayır. Dağ silsiləsini tam keçmək üçün o, yuxarıda təsvir edilən üç əməliyyatdan birini ardıcıl olaraq yerinə yetirərək bütün $n$ zirvələrini ən azı bir dəfə ziyarət etməlidir. Hər bir $j$ üçün, Conun bütün dağ silsiləsini keçməsi üçün ödəməli olduğu minimum frank miqdarını müəyyən edin. (Bu xərc $j$-ci fənərin ilkin alış qiymətini də əhatə edir.)