D. Баавгай ба хувь нэмэр-оноо

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

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

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

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

Кодфорсес хэмээх гайхалтай платформд хүн бүр хэр хэмжээний хувь нэмэр (contribution) оруулсан нь харагддаг билээ. Бүртгэлтэй гишүүн бүр оруулсан хувь нэмэр болох бүхэл тоон утгатай ба энэ нь заавал эерэг байх албагүй юм. Нийт $n$ бүртгэлтэй гишүүд байгаа ба $i$ дэх нь $t_{i}$ хэмжээний хувь нэмэр оруулсан байг.

Лимак гэх бяцхан цагаан баавгай програмчлалын тэмцээнтэй танилцаж буй аж. Түүнд Кодфорсес хаяг байхгүй ч одоо байгаа блог болон сэтгэгдлүүдийг уншиж оноог нь өсгөх боломжтой. Бүртгэлтэй гишүүн бүр тоо томшгүй олон блог, комментуудтай гэж үзье.

  • Лимак нэг блогийг $b$ минутанд уншиж, оноог нь өсгөх боломжтой. Тэгэхэд зохиогчийн оруулсан хувь нэмэр (contribution) буюу оноо $5$-аар өснө. .
  • Лимак нэг сэтгэгдлийг $c$ минутанд уншиж оноог нь өсгөх боломжтой. Зохиогчийн оноо $1$-ээр өснө.

Лимак блогийг сэтгэгдлээс хурдан уншдаг байх боломжтойг тэмдэглэе.

Лимак тэнцээ харах дуртай. Ядаж $k$ ширхэг бүртгэлтэй хэрэглэгчид адил тэнцүү оноотой байвал гоё доо гэж тэр бодож байгаа аж. Ингэхийн тулд тэрээр зарим зүйлсийг уншиж, оноог нь өсгөхөд тодорхой цаг зарна. Үүний дараа ядаж $k$ ширхэг бүртгэлтэй хэрэглэгчид яг $x$ оноотой байх $x$ олддог байх ёстой. \

Зорилгодоо хүрэхэд Лимакт хэдий хэрийн хугацаа шаардлагатай вэ?

Оролт

Эхний мөрөнд $n$, $k$, $b$, $c$ ($2 \le k \le n \le 200 000, 1 \le b, c \le 1000$) тоонууд өгөгдөнө, харгалзан бүртгэлтэй хэрэглэгчийн тоо, хэдэн хэрэглэгч ижил оноотой байх шаардлатай тоо, блог унших хугацаа, сэтгэгдэл унших хугацааг тус тус илтгэнэ.

Хоёр дах мөрөнд $t_{1}, t_{2}, ..., t_{n}$ ($|t_{i}| \le 10^{9}$) $n$ ширхэг тоонууд өгөгдөх ба $t_{i}$ нь $i$ дэх хэрэглэгчийн оноог илэрхийлнэ.

Гаралт

Лимак баавгай ядаж $k$ ширхэг гишүүдийн оноог тэнцүүлэхийн тулд хамгийн багадаа хэдэн минут зарцуулахыг хэвлэнэ үү.

Орчуулсан: Төрбат

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

Оролт
4 3 100 30
12 2 6 1
Гаралт
220
Оролт
4 3 30 100
12 2 6 1
Гаралт
190
Оролт
6 2 987 789
-8 42 -4 -65 -8 -8
Гаралт
0

Тэмдэглэл

Эхний жишээнд $4$ бүртгэлтэй хэрэглэгч байх ба Лимак $3$ гишүүдийн оноог тэнцүүлэхийг хүсч байгаа. Лимак дараах байдлаар ажиллавал зохино:

  • $4$ дэх хэрэглэгчийн блогийг $100$ минут уншиж оноог нь $1$-ээс $6$-руу өсгөнө.
  • Харин дөрвөн сэтгэгдэл $4*30 = 120$ минут уншиж $2$-р хэрэглэгчийн оноог $2$-оос $6$-руу өсгөнө. (Дөрвөн удаа $1$-ээр өсгөж буй хэрэг)

Энэ хувилбараар Лимак $100 + 4*30 = 220$ минут зарцуулж $2, 3, 4$ хэрэглэгчдийн оноог адил $6$ болгох боломжтой.

Хоёр дах жишээнд Лимак блог уншихад $30$, сэтгэгдэл уншихад $100$ минут зарцуулна. Энэ удаад тэрээр $100 + 3*30 = 190$ хугацаа зарцуулж $3$ хэрэглэгчийн оноог $12$ хүргэж чадна:

  • $2*30 = 60$ минут зарцуулж эхний хэрэглэгчийн оноог $2$-оос $12$ хүргэнэ.
  • $30 + 100$ минут зарцуулан нэг блог, нэг сэтгэгдэл уншин $3$-р хэрэглэгчийн оноо $6$-аас $6 + 5 + 1 = 12$ болно.
Сэтгэгдлүүдийг ачааллаж байна...