Masala #GC4TZHIPJZ

Xotira 32 MB Vaqt 1000 ms

Sehrgar Malik

Bir zamonlar sehrli shaharlar o‘lkasi bo‘lgan. Bu o‘lka 7 ta shaharni o‘z ichiga olgan va bu shaharlarni sehrli yo‘llar bog‘lab turgan. Sehrgar Malik ushbu o‘lkada sayohat qilishni niyat qilgan. Lekin u har bir shaharni faqat bir marta ziyorat qilishi va so‘ng yana boshlang‘ich shaharga qaytishi kerak.

Sehrli yo‘llarning har birida qanchadir vaqt (masalan, soatlar) ketadi. Malikning vazifasi – barcha shaharlarni ziyorat qilib, yo‘lda minimal vaqt sarflash.

Kiruvchi ma'lumotlar:

1-qatorda u borishi kerak bo'lgan shaharlar va ularni bog'lab turgan yo'llar soni \(M\) beriladi.

Keyingi \(M\)ta qatorda yo'lning boshlanish tugash va qancha vaqt ketishi aytilgan.

So'ngi qatorda boshlang'ich shahar berilgan.

Chiquvchi ma'lumotlar:

Minimum vaqtni chop eting.

Misollar

#	input.txt	output.txt
1	A B C D E 10 A B 2 A C 9 A D 10 A E 7 B C 6 B D 4 B E 3 C D 8 C E 5 D E 1 A	23