İltifatlar#2602

İltifatlar

1 saniye
128 megabayt

Anya, Vanya'ya onun moralini olabildiğince çok yükseltecek bir mesaj yazmak istiyor. Vanya iltifat biliyor. Her iltifat, küçük Latin harflerinden oluşan boş olmayan bir dizgidir. Bazı iltifatlar aynı şekilde yazılabilir: bunlar yazılışları aynı olan farklı iltifatlardır.

Başlangıçta Vanya'nın morali 'dır. -inci iltifat mesajda bitişik bir alt dizgi olarak her geçtiğinde, Vanya'nın morali a_i kadar artar. Geçişler çakışabilir ve her biri ayrı ayrı sayılır. Örneğin, mesajında dizgisi iki kez, dizgisi ise bir kez geçer.

Mesaj en fazla karakter içerebilir. Vanya'nın mesajı okuduktan sonra moralinin ulaşabileceği en büyük değeri bulun.

Giriş

İlk satırda iki tam sayı ve l~(1 \le n \le 200, 1 \le l \le 10^{14}) verilir — iltifatların sayısı ve mesajın izin verilen en büyük uzunluğu.

İkinci satırda tam sayı a_1, a_2, \ldots, a_n~(1 \le a_i \le 100) verilir. a_i sayısı, -inci iltifatın her geçişinde Vanya'nın moralinin ne kadar arttığını gösterir.

Sonraki satırın her birinde bir iltifat verilir: bunlardan -incisinde küçük Latin harflerinden oluşan boş olmayan bir s_i dizgisi bulunur. Tüm s_i dizgilerinin toplam uzunluğu 'ü geçmez.

Çıktı

Tek bir tam sayı yazdırın — Vanya'nın moralinin mümkün olan en büyük değeri.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Not

Birinci örnekte mesajı uygundur: her iltifat onda tam olarak bir kez geçer ve moral 3 + 2 + 1 = 6 olur.

İkinci örnekte artart mesajı uygundur: iltifatı onda iki kez geçer ve moral 8 + 8 = 16 olur.