Anya Vanyaya onun əhvalını mümkün qədər çox yaxşılaşdıracaq bir mesaj yazmaq istəyir. Vanya kompliment bilir. Hər kompliment kiçik latın hərflərindən ibarət boş olmayan sətirdir. Bəzi komplimentlər eyni cür yazıla bilər: bunlar eyni şəkildə yazılan müxtəlif komplimentlərdir.
Əvvəlcə Vanyanın əhvalı -a bərabərdir. Mesajda -ci komplimentə kəsilməz altsətir kimi hər dəfə rast gəldikdə, Vanyanın əhvalı a_i qədər artır. Rastgəlmələr üst-üstə düşə bilər və onların hər biri ayrıca hesablanır. Məsələn, mesajında sətrinə iki dəfə, sətrinə isə bir dəfə rast gəlinir.
Mesaj ən çoxu simvoldan ibarət ola bilər. Mesajı oxuduqdan sonra Vanyanın əhvalının çata biləcəyi ən böyük qiyməti tapın.
Birinci sətirdə iki tam ədəd və l~(1 \le n \le 200, 1 \le l \le 10^{14}) verilir — komplimentlərin sayı və mesajın icazə verilən ən böyük uzunluğu.
İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n~(1 \le a_i \le 100) verilir. a_i ədədi -ci komplimentin hər rastgəlməsində Vanyanın əhvalının nə qədər artdığını göstərir.
Sonrakı sətrin hər birində bir kompliment verilir: onlardan -cisində kiçik latın hərflərindən ibarət boş olmayan s_i sətri verilir. Bütün s_i sətirlərinin ümumi uzunluğu -dən çox deyil.
Bir tam ədəd çıxarın — Vanyanın əhvalının mümkün olan ən böyük qiyməti.
Nümunə 1
Nümunə 2
Birinci nümunədə mesajı uyğun gəlir: hər komplimentə orada düz bir dəfə rast gəlinir və əhval 3 + 2 + 1 = 6-ya bərabərdir.
İkinci nümunədə artart mesajı uyğun gəlir: komplimentinə orada iki dəfə rast gəlinir və əhval 8 + 8 = 16-ya bərabərdir.