Aviabiletlərin qiyməti

Çiplərin qiymətləri bir həftədən digərinə çox dəyişir və bu gözlənilməzlik səyahətçilər üçün əsas məyusluq mənbəyidir. Bəzi səyahətçilər biletləri çox tez aldıqlarına görə peşman olurlar, çünki qiymətlər onlar biletləri aldıqdan sonra dərhal düşür. Digərləri isə biletləri çox gec aldıqlarına görə peşman olurlar, çünki qiymətlər alış etməyə hazırlaşmadan əvvəl artır. Nəticədə, heç kim razı qalmır, əlbəttə ki, aviaşirkətlərdən başqa.

Bu çılğınlığın bir səbəbi var. Məlum olur ki, aviaşirkətlər biletlərin qiymətlərini dinamik olaraq dəyişirlər, mövcud yerlərin sayına və uçuşun nə qədər yaxın olduğuna əsaslanaraq. Məsələn, əgər uçuşda çox az yer qalıbsa, biletlər baha ola bilər, lakin uçuşa son bir neçə həftə qalmış qiymətlər boş yerləri doldurmaq üçün azala bilər. Nəticədə, aviaşirkətlər hər uçuşdan əldə olunan gəliri maksimuma çatdırmaq istəyirlər.

Sizi International Contrived Pricing Corporation (ICPC) şirkəti aviaşirkətlər üçün hər həftə bilet qiymətlərini təyin etmək üçün işə götürüb. Aviaşirkətlər tarixi məlumatları toplayıb və analiz ediblər və müəyyən bilet qiymətinə və uçuşa qalan həftələrin sayına görə satılacaq yerlərin sayını yaxşı qiymətləndiriblər. Uçuşda qalan yerlərin sayını və uçuşa qalan həftələrin sayını nəzərə alaraq, cari həftədən uçuşun başlanğıcına qədər bilet satışından əldə olunan ümumi gəliri maksimuma çatdırmaq üçün cari həftə üçün bilet qiymətini təyin etməlisiniz. Qalan yerlər kifayət qədər olduğu halda, satılan bilet sayı dəqiq olaraq qiymətləndirilənə bərabər olacaq. Son halda, bütün qalan yerlər satılacaq. Həmçinin, uçuşun başlanğıcına qalan həftələr üçün optimal bilet qiymətləri seçiləcək.

Qeyd edin ki, daha yüksək qiymətlər mütləq daha az bilet satışı demək deyil. Əslində, daha yüksək qiymətlər bəzən satışları artıra bilər, çünki səyahətçilər qiymətlərin daha da artacağından narahat ola bilərlər.

Giriş Məlumatları

Birinci sətir iki tam ədəd n və w (0 < n ≤ 300, 0 ≤ w ≤ 52) - qalan yerlərin sayı və uçuşa qalan həftələrin sayını ehtiva edir. Növbəti w + 1 sətir w həftə, w - 1 həftə, . . ., və s. uçuşa qalan 0 həftəyə (yəni son həftəyə) qədər qiymətləndirmələri verir. Bu sətirlərin hər biri cari həftə üçün qiymətlərin sayını göstərən k (0 < k ≤ 100) ədədi ilə başlayır. Sonra k tam ədədlər 0 < p[1] < . . . < p[k] < 1000 dollarla qiymətləri göstərir. Daha sonra müvafiq qiymətlərə görə satılacaq bilet sayını göstərən k əlavə tam ədədlər s[1], ..., s[k] (0 ≤ s[i] ≤ n) gəlir.

Çıxış Məlumatları

Birinci sətirdə aviaşirkətlərin cari həftədən uçuş vaxtına qədər bilet satışından əldə edə biləcəyi maksimum ümumi gəliri göstərin. İkinci sətirdə bu maksimuma çatmaq üçün cari həftə (w həftə uçuşa qalmış) təyin edilməli olan bilet qiymətini göstərin.

Əgər maksimuma çatmaq üçün bir neçə bilet qiymət dəsti varsa, w həftə üçün ən kiçik bilet qiymətini seçmək lazımdır.