B. Элчин сайдын яамны дараалал

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэгэн улсын элчин сайдын яаманд цахим бүртгэл явагдаж байна. Элчин сайдын яаманд ирсэн хүн бүр дараах 3 үйлдлийг хийх хэрэгтэй: иргэний үнэмлэхээ шалгуулах, кассад мөнгөө тушаах ба хурууны хээгээ бүртгүүлэх. Түүнчлэн эдгээр үйлдлийг өгсөн дарааллын дагуу гүйцэтгэх хэрэгтэй.

Үйлдэл бүрийг гүйцэтгэх тусгай цонхнуудтай: Эхний үйлдлийг хийх $k_{1}$ ширхэг тусгай цонхтой (эхний төрлийн цонх), хоёрдох үйлдлийг хийх $k_{2}$ ширхэг тусгай цонхтой (хоёрдугаар төрлийн цонх), гурав дахь үйлдлийг хийх $k_{3}$ ширхэг тусгай цонхтой (гуравдугаар төрлийн цонх). Нэг хүний эхний төрлийн аль ч цонхонд үйлчлүүлэхэд зарцуулах хугацаа нь $t_{1}$. Мөн адил хоёрдугаар төрлийн аль ч цонхонд үйлчлүүлэхэд зарцуулах хугацаа нь $t_{2}$, гуравдугаар төрлийн аль ч цонхонд үйлчлүүлэхэд зарцуулах хугацаа нь $t_{3}$. Иймд үйлчилгээнд зарцуулах хугацаа нь цонхны төрлөөс л хамаарна, үйлчлүүлэгч нь ямар хүн гэдгээс хамаарахгүй.

Элчин сайдын яаманд $n$ хүн ирсэн ба $i$-р хүн $c_{i}$ цагт ирсэн. Ирсэн хүн ямар нэг дугаар аваад, авсан дугаар нь тусгай самбар дээр гартал танхимд сууж хүлээнэ. Түүнчлэн самбар дээр цонхны дугаар болон яг аль цонх уруу нь очих хэрэгтэйг харуулах ба үйлчлүүлэгч нэн даруй очно. Цонх уруу очиход ямар ч хугацаа шаардахгүй гэж үзье. Самбар нэг мөчид 1-с олон хүний мэдээллийг харуулж чадахгүй. Үйлчлүүлэгчийг цонхон дээр ирэхэд нэн даруй үйлчилж эхлэх ба тэр цонхон дээр ямар ч оочиргүй байна.

Үйлчилгээний чанарыг шалгагч байцаагч зарим хүмүүс элчин сайдын яаманд хэтэрхий их цагийг дэмий үрж байна гэж үзэв. (элчин сайдын яаманд ямар ч утасны сүлжээ ба 3G байхгүй тул их уйтгартай). Тиймээс элчин сайдын яаманд хамгийн их цагийг зарцуулах хүний хугацаа нь хамгийн бага байхаар системийг зохион байгуулахаар шийдэв. Байцаагчид дарааллыг зохион байгуулахад нь тусал. Аль ч цонхон дээр очиход ямар ч хугацаа шаардахгүй гэж үзнэ.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 3 бүхэл тоо $k_{1}$, $k_{2}$, $k_{3}$ ($1 ≤ k_{i} ≤ 10^{9}$) өгөгдөнө -- харгалзан нэг, хоёр ба гуравдугаар төрлийн цонхны тоог илэрхийлнэ.

Хоёрдох мөрөнд зайгаар тусгаарлагдсан 3 бүхэл тоо $t_{1}$, $t_{2}$, $t_{3}$ ($1 ≤ t_{i} ≤ 10^{5}$) харгалзан нэг, хоёр ба гуравдугаар төрлийн цонхонд үйлчлүүлэхэд зарцуулах хугацаа өгөгдөнө.

Гурав дахь мөрөнд үйлчлүүлэгчдийн тоог илэрхийлэх $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоо өгөгдөнө.

Дөрөвдэхь мөрөнд үл буурах дарааллаар зайгаар тусгаарлагдан $c_{i}$ ($1 ≤ c_{i} ≤ 10^{9}$) тоонууд өгөгдөнө. $c_{i}$ нь $i$-р хүн элчин сайдын яаманд ирсэн цаг.

Гаралт

Ганц тоо хэвлэнэ, дарааллыг хамгийн сайнаар нь зохион байгуулахад үйлчлүүлэгчдээс элчин сайдын яаманд зарцуулах хамгийн их хугацаа.

С++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг бүү хэрэглэнэ үү. Үүний оронд cin, cout streams болон %I64d тодорхойлогчийг хэрэглэхийг илүүд үзнэ үү.

Орчуулсан: Б.Алтангэрэл

Жишээ тэстүүд

Оролт
1 1 1
1 1 1
5
1 1 1 1 1
Гаралт
7
Оролт
2 1 1
5 1 1
5
1 2 3 3 5
Гаралт
13

Тэмдэглэл

Эхний жишээн дээр 5 хүн нэгэн зэрэг цаг 1 болж байхад ирнэ. Төрөл бүрээс нэг цонх байх ба үйлчлүүлэхэд 1 нэгж хугацаа зарцуулна. Яагаад хамгийн их хугацаа нь вэ гэвэл цонхнуудад үйлчлүүлэхэд 3 нэгж хугацаа зарцуулна нэмээд сүүлийн хүн эхний цонхон дээр очих хүртлээ 4 нэгж хугацаа хүлээнэ.

Хоёрдох жишээнд цонхнууд доор үзүүлсэн шиг ажиллана:

Нэгдүгээр төрлийн эхний цонх: $[1, 6)$ -- 1-р хүн, $[6, 11)$ -- 3-р хүн, $[11, 16)$ -- 5-р хүн

Нэгдүгээр төрлийн хоёрдох цонх: $[2, 7)$ -- 2-р хүн, $[7, 12)$$ -- 4-р хүн

Хоёрдугаар төрлийн ганц цонх: $[6, 7)$ -- 1-р, $[7, 8)$ -- 2-р, $[11, 12)$ -- 3-р, $[12, 13)$ -- 4-р, $[16, 17)$ -- 5-р

Гуравдугаар төрлийн ганц цонх: $[7, 8)$ -- 1-р, $[8, 9)$ -- 2-р, $[12, 13)$ -- 3-р, $[13, 14)$ -- 4-р, $[17, 18)$ -- 5-р

Ингэж зохион байгуулбал 5-р хүн хамгийн их цагийг үйлчлүүлэхдээ зарцуулна.

Сэтгэгдлүүдийг ачааллаж байна...