Konfet zənciri
Konfet zənciri - fərqli konfetlərin ardıcıllığıdır. Bu konfetlər 26 müxtəlif dadı təmsil edir və kiçik hərflərlə a-dan z-ə qədər göstərilir. Marqonun mağazasında qeyri-adi bir konfet zənciri sərgilənir.
Məktəbdən sonra uşaqlar mağazaya gələcək və konfet zəncirindən parçalar alacaqlar. Hər bir uşağın özünəməxsus üstünlükləri var. Məsələn, ababi dadını sevən bir uşaq var və buna görə 3 avro ödəməyə hazırdır. Başqa bir uşaq isə axsa dadını sevir və buna görə 5 avro ödəməyə hazırdır.
Marqo konfet zəncirindən parçalar çıxarıb uşaqlara sata bilər. O, bir porsiyanı çıxardıqda, qalan sol və sağ konfet zəncirini birləşdirir və sonra növbəti porsiyaları təqdim etməyə davam edir və ya dayanır.
Eyni dad ardıcıllığı bir neçə dəfə eyni uşağa satıla bilər (Marqo bu dadı konfet zəncirindən bir neçə dəfə çıxara bilsə). Marqo konfetləri satmaq üçün atmır. O, konfet porsiyalarını satarkən dəyişə bilər (məsələn, axsa və asxa ekvivalentdir). Marqo bütün uşaqlara xidmət etməyə məcbur deyil və müəyyən bir qaydada uşaqlara xidmət etməyə məcbur deyil.
Sizin vəzifəniz - Marqoya konfet zəncirindən maksimum məbləği necə qazana biləcəyini hesablamağa kömək etməkdir.
Giriş məlumatları
Birinci sətir Marqonun konfet zəncirini boş olmayan simvol sətiri şəklində təqdim edir. İkinci sətir uşaqların sayı c (1 ≤ c ≤ 200) göstərir. Növbəti c sətir hər bir uşağın üstünlüklərini iki element şəklində təqdim edir, boşluqla ayrılmış: onun üstünlük verdiyi konfet porsiyası boş olmayan simvol sətiri ilə təqdim olunur; və onun ödəməyə hazır olduğu məbləğ tam ədəd P[i] (0 ≤ P[i] ≤ 10^6 for all 1 ≤ i ≤ c).
Bütün sətirlər yalnız a-dan z-ə qədər kiçik hərflərdən ibarətdir. Marqonun konfet zənciri və hər bir uşağın konfet porsiyası ən çox 50 konfetdən ibarətdir.
Çıxış məlumatları
Bir tam ədəd çıxarın - Marqonun qazana biləcəyi maksimum məbləğ.