Kirayə xidmətləri#10421

Kirayə xidmətləri

1 saniyə

128 meqabayt

Orta

Fermer Con başa düşür ki, süd istehsalından əldə etdiyi gəlir fermasının inkişafını maliyyələşdirmək üçün kifayət deyil, buna görə də əlavə pul qazanmaq üçün inəklərin icarəsi xidmətini açır və onu "USACOW" ("Use-a-cow" kimi tələffüz olunur) adlandırır.

Fermer Conun $n$ inəyi var, onların hər biri hər gün müəyyən miqdarda süd verə bilir. Fermer Conun fermasının yaxınlığındakı $m$ mağazanı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 fermerinin hər biri müəyyən qiymətə bir inək icarəyə götürmək istəyir.

Fermer Con hər bir inək üçün qərar verməlidir: onu sağmaq, yoxsa qonşu fermerə icarəyə vermək. Ona bir gündə qazana biləcəyi maksimum pul məbləğini tapmağa kömək edin.

Giriş

Birinci sətirdə üç tam ədəd $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5), $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5) və $r (1 \leq r \leq 1 0^{5})$ r~(1 \le r \le 10^5) verilir. Növbəti $n$ sətrin hər birində bir tam ədəd $c_{i} (1 \leq c_{i} \leq 1 0^{6})$ c_i~(1 \le c_i \le 10^6) verilir; bu, Fermer Conun $i$ -ci inəyinin hər gün $c_{i}$ c_i qallon süd verə bildiyini göstərir. Növbəti $m$ sətrin hər birində iki tam ədəd $q_{i}$ q_i və $p_{i} (1 \leq q_{i}, p_{i} \leq 1 0^{6})$ p_i~(1 \le q_i, p_i \le 10^6) verilir; bu, $i$ -ci mağazanın hər qallonu $p_{i}$ p_i sentə olmaqla $q_{i}$ q_i qallona qədər süd almağa hazır olduğunu göstərir. Nəzərə alın ki, Fermer Con hər hansı mağazaya sıfırdan $q_{i}$ q_i qallona qədər istənilən miqdarda süd sata bilər. Növbəti $r$ sətrin hər birində bir tam ədəd $r_{i} (1 \leq r_{i} \leq 1 0^{6})$ r_i~(1 \le r_i \le 10^6) verilir; bu, Fermer Conun qonşularından birinin gündə $r_{i}$ r_i sentə bir inək icarəyə götürmək istədiyini göstərir.

Çıxış

Bir tam ədəd çap edin: Fermer Conun inəklərinin hər birini sağmaqla və ya icarəyə verməklə bir gündə əldə edə biləcəyi maksimum gəlir. Nəzərə alın ki, cavab standart 32-bitlik tam ədəd tipinə sığmaya bilər, buna görə də daha böyük tam ədəd tipindən, məsələn, C/C++ dilində "long long" tipindən istifadə etməyiniz lazım ola bilər.

Nümunələr

Nümunə 1

Qeyd

Fermer Con $1$ və $4$ nömrəli inəkləri sağıb $13$ qallon süd əldə etməlidir. O, $10$ qallonluq sifarişi tam yerinə yetirərək $250$ sent qazanmalı və qalan üç qallonu hər birini $15$ sentə satmalıdır; beləliklə, süddən ümumi gəlir $295$ sent olur.

Sonra o, qalan üç inəyi $250$ , $80$ və $100$ sentə icarəyə verərək daha $430$ sent qazanmalıdır. ( $40$ sentlik icarə təklifini o, yerinə yetirməməlidir.) Nəticədə gündəlik ümumi gəlir $725$ sent olur.