C. Арслангийн эрин II

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

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

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

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

Вася "Арслангийн эрин II" (LionAge II) тоглоомоор тоглож удсан тул компьютер өрсөлдөгчөө төвөггүй ялдаг болсон тул уйдаж онлайнаар найзуудтайгаа тоглохоор болов. Васягийн баатрын нэр нь латин жижиг үсгүүдээс бүтсэн хоосон зай агуулаагүй $s$ тэмдэгт мөрнөөс тогтоно. Гэхдээ Вася нэрсийн жагсаалтад найзуудаасаа дээгүүрт жагсахын тулд хамгийн ихдээ $k$ тэмдэгт солих замаар өөрчлөхөөр шийдсэн ба шинэ нэр нь сонсголонтой байхыг чухалчилжээ.

Дарааллаж орсон $x$, $y$ үсэг бүрийн хувьд $c(x, y)$ гэсэн сонсголонтой байдлын оноо байдаг гэвэл, үүнийг ашиглаад аливаа нэрийн нийт сонсголонг тооцож болно. Хамгийн ихдээ $k$ ширхэг тэмдэгт солиод боломжит хамгийн өндөр сонсголонтой нэрийг Васяд олж өгч тусална уу.

Оролт

Эхний мөрөнд баатрын нэр $s$ болон солих тэмдэгтийн тоо $k$ ($0 ≤ k ≤ 100$) байна. Баатрын нэр хоосон биш байх бөгөөд урт нь $100$-аас хэтрэхгүй.

Хоёр дахь мөрөнд бүхэл тоо $n$ ($0 ≤ n ≤ 676$) байрлана. Дараагийн $n$ мөрөнд мөр бүрд «$x$ $y$ $c$» ($x, y$ нь латин жижиг үсгүүд, $-1000 ≤ c ≤ 1000)$ гэсэн гурвал байх бөгөөд энэ нь дарааллан орсон $x$, $y$ үсгүүдийн сонсголонгийн оноо $c$ юм.

Оролтын өгөгдөлд $x$, $y$ хос давхардаж орохгүй.

Гаралт

Шинэ нэрэнд оногдож боломжит хамгийн өндөр сонсголонгийн оноо.

Орчуулсан: gmunkhbaatarmn

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

Оролт
winner 4
4
s e 7
o s 8
l o 13
o o 8
Гаралт
36
Оролт
abcdef 1
5
a b -10
b c 5
c d 5
d e 5
e f 5
Гаралт
20

Тэмдэглэл

Эхний жишээн дээр хамгийн сонсголонтой нэр нь "looser", оноо нь 36 байна.

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