Video-kafe Ujlandiyada#7243

Video-kafe Ujlandiyada

1,5 saniyə

128 meqabayt

Çətin

Məlum olduğu kimi, 2014-cü il dünya xokkey çempionatı Ujləndiyada keçiriləcək. Turnirin uğurla keçməsi üçün təşkilatçı ölkə Beynəlxalq Xokkey Federasiyasının bir sıra tələblərinə əməl etməlidir. Xokkey oyunları Ujkaçevo və Ujkovel şəhərlərində keçiriləcək və bu şəhərlər birbaşa avtomagistralla birləşir.

Qeyd olunub ki, Ujkaçevo — Ujkovel şosesi boyunca yerləşən $N$ turist düşərgəsinin heç birində hazırda video-kafe yoxdur. Video-kafe – demək olar ki, adi yolkənarı kafedir, lakin idman tədbirlərinin yayımı üçün avadanlıqla təchiz olunmuşdur. Federasiya qərara alıb ki, $N$ düşərgənin $K$ -sində aşağıdakı qaydalara əsasən video-kafe qurulmalıdır:

1. İstənilən video-kafe ilə yol boyunca əvvəlki video-kafe arasında (əgər belə varsa) məsafə ən az $A$ km və ən çox $B$ km olmalıdır. 2. İstənilən video-kafe ilə sonrakı video-kafe arasında (əgər belə varsa) məsafə ən az $A$ km və ən çox $B$ km olmalıdır.

3. Hər iki şəhərin hər birindən ən yaxın video-kafeyə olan məsafə də daxil olmaqla $A$ -dan $B$ -yə qədər (hər ikisi daxil olmaqla) olmalıdır.

Şəkildə: $N = 5$ N = 5, $K = 3$ K = 3, $A = 20$ A = 20, $B = 70$ B = 70.

Hər $i$ -ci video-kafe üçün $Z_{i}$ Z_i əmsalını — bu kafenin digər bütün video-kafelərə olan məsafələrinin cəmini müəyyən edək. Bütün $Z_{i}$ Z_i əmsallarının cəmi nə qədər böyük olsa, turistlər matçlar barədə informasiyanı bir o qədər operativ alacaqlar.

Sizin tapşırığınız — tələblərə uyğun olaraq $K$ video-kafe yerləşdirilməsi üçün $Z_{i}$ Z_i əmsallarının mümkün olan ən böyük cəmini müəyyənləşdirməkdir. Hər bir düşərgədə yalnız bir video-kafe tikilə bilər və yalnız düşərgələrdə video-kafe qurmaq olar.

Giriş

Birinci sətirdə iki tam ədəd — $N, K$ $(1 \leq K \leq N \leq 1000)$ (1 \le K \le N \le 1000) verilir.

İkinci sətirdə iki tam ədəd $A, B$ $(1 \leq A < B \leq 1 0^{9})$ (1 \le A < B \le 10^{9}) göstərilir.

Üçüncü sətirdə bir tam ədəd $S$ $(1 \leq S \leq 1 0^{9})$ (1 \le S \le 10^{9}) — Ujkaçevo ilə Ujkovel arasındakı məsafə verilir.

Dördüncü sətirdə $N$ ədəd tam ədəd $C_{i}$ C_i $(0 < C_{i} < S, C_{i} < C_{j} əgər i < j)$ (0 < C_i < S, C_i < C_j\ \text{əgər}\ i < j) — $i$ -ci düşərgəyə Ujkaçevodan olan məsafələr göstərilir.

Çıxış

Bir ədəd çıxış verin — $K$ video-kafe üçün $Z_{i}$ Z_i əmsallarının mümkün olan ən böyük cəmi. Həmişə həll mövcuddur.

Nümunələr

Nümunə


5 3
20 70
90
20 40 70 80 85

Nümunə


10 4
10 35
100
8 12 22 25 37 45 62 75 86 90

Nümunə 1

Qeyd

Birinci nümunədə düşərgələrdən ${1, 2, 4}$ \{1, 2, 4\} seçilmişdir.

İkinci nümunədə isə ${2, 5, 8, 10}$ \{2, 5, 8, 10\} seçilmişdir.