Чудна мрежа
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 0,1 s | 64 Mb | standardni izlaz | standardni ulaz |
У једном рачунарском кабинету потребно је успоставити необичну рачунарску мрежу. Потребно је поставити рачунаре на \(n\) столова, при чему на неким столовима могу да стоје обични рачунари (њих имамо на располагању у неограниченом броју), а на неким посебни сервери (њих посебно морамо купити по цени од \(c_s\) динара). Неке столове је могуће повезати директно мрежним кабловима, а неке није. Цена успостављања мрежног кабла између било која два стола је \(c_k\) динара. Написати програм који одређује најмању цену коју је потребно платити тако да је сваки рачунар или сервер или је мрежним каблом повезан са бар једним сервером (не обавезно директно).
Улаз
Са стандардног улаза се у првом реду уносе бројеви \(c_s\) (\(0 \leq c_s \leq 1000\)) и \(c_k\) (\(0\leq c_k \leq 1000\)), раздвојени размаком. У наредном реду се уноси број столова \(n\) (\(2 \leq n \leq 50000\)) и \(m\) број парова столова између којих је могуће поставити мрежни кабл \(2 \leq m \leq \frac{n(n-1)}{2}\), раздвојени размаком. У наредних \(m\) редова уносе се парови бројева између \(0\) и \(n-1\), раздвојених размаком који одређују столове између којих је могуће поставити кабл.
Излаз
На стандардни излаз исписати тражену најмању цену.
Пример
Улаз
850 350 7 6 0 1 0 4 4 2 1 4 3 5 6 5
Излаз
3450
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.