Kirayə xidmətləri
Fermer Con, süd istehsalından əldə etdiyi gəlirin fermasının böyüməsini maliyyələşdirmək üçün kifayət etmədiyini başa düşür və buna görə də əlavə pul qazanmaq məqsədilə "USACOW" (oxunuşu "Use-a-cow") adlandırdığı inək icarəsi xidmətini işə salır.
Fermer Conun n inəyi var və hər biri hər gün müəyyən miqdarda süd verə bilər. Fermaya yaxın olan m mağazaların hər biri müəyyən miqdarda südü müəyyən qiymətə almağı təklif edir. Bundan əlavə, fermer Conun r qonşu fermerləri müəyyən qiymətə inək icarəyə götürməkdə maraqlıdır.
Fermer Con hər bir inəyi sağmaq və ya qonşu fermerə icarəyə vermək arasında seçim etməlidir. Ona gündə maksimum nə qədər pul qazana biləcəyini tapmağa kömək edin.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5), m (1 ≤ m ≤ 10^5) və r (1 ≤ r ≤ 10^5) ədədlərini ehtiva edir. Növbəti n sətirin hər biri c[i] (1 ≤ c[i] ≤ 10^6) tam ədədini ehtiva edir, bu da Conun i-ci inəyinin hər gün c[i] gallon süd istehsal edə biləcəyini göstərir. Növbəti m sətirdə hər biri iki tam ədəd q[i] və p[i] (1 ≤ q[i], p[i] ≤ 10^6) var, bu da i-ci mağazanın q[i] gallon südü p[i] qiymətinə almağa hazır olduğunu göstərir. Qeyd edin ki, Con hər hansı bir mağazaya sıfırdan q[i] gallonadək süd sata bilər. Növbəti r sətirin hər biri r[i] (1 ≤ r[i] ≤ 10^6) tam ədədini ehtiva edir, bu da fermer Conun qonşularından birinin gündə r[i] sentə inək icarəyə götürmək istədiyini göstərir.
Çıxış Məlumatları
Fermer Conun hər bir inəyi sağmaq və ya icarəyə verməkdən gündəlik maksimum qazancını göstərin. Qeyd edin ki, çıxış standart 32-bit tam ədəd üçün çox böyük ola bilər, buna görə C/C++-da long long kimi daha böyük tam ədəd tipindən istifadə etməyiniz lazım ola bilər.
Nümunə
Fermer Con #1 və #4 inəklərini sağmalı və 13 gallon süd istehsal etməlidir. O, 10 gallon sifarişi tam yerinə yetirməli və 250 sent qazanmalı, qalan üç gallon südü isə hər biri 15 sentə sataraq ümumilikdə 295 sent süd qazancı əldə etməlidir.
Sonra o, qalan üç inəyi 250, 80 və 100 sentə icarəyə verməli və 430 sent qazanmalıdır (o, 40 sent icarə təklifini yerinə yetirməməlidir). Ümumilikdə 725 sent gündəlik qazanc əldə edəcək.