Mutasiya#2011

Mutasiya

2 saniyə

256 meqabayt

Orta

Olimpiya planetində alimlər ibtidai orqanizmlərin mutasiyası üzərində təcrübə aparırlar. Bu planetdən olan bir orqanizmin genomu İngilis əlifbasının ilk $K$ böyük hərfindən ibarət olan bir sətirlə təsvir edilə bilər. Hər bir gen cütü üçün, genomda bu növlər yanaşı olduqda xəstəlik yaranma riski müəyyən edilmişdir. Orqanizmin ümumi xəstəlik riski, genomda qonşu olan hər bir gen cütü üçün risklərin cəminə bərabərdir və riskoqramlarla ölçülür.

Alimlər baza orqanizmi əldə etmişlər və digər orqanizmləri bu orqanizmdən mutasiya yolu ilə çıxara bilirlər. Bu mutasiya isə müəyyən gen növlərinin hamısının silinməsi ilə həyata keçirilir. Belə çıxarılma xəstəlik riskini artırır və hər bir gen növü üçün, onun çıxarılması nəticəsində xəstəlik riskinin nə qədər artdığı göstərilmişdir. Alimlər maraqlanır ki, baza orqanizmindən bu üsulla xəstəlik riski $T$ riskoqramı aşmayan neçə müxtəlif orqanizm almaq mümkündür. İki orqanizm genom sətirləri fərqlidirsə, müxtəlif sayılırlar. Əldə edilən orqanizmin genomunda ən azı bir gen olmalıdır.

Verilənlər üzrə, baza orqanizminin genomunu və xəstəlik riski parametrlərini nəzərə alaraq, xəstəlik riski $T$ -dən çox olmayan neçə müxtəlif orqanizmin əldə edilə biləcəyini müəyyən edən proqram yazın.

Giriş

Birinci sətirdə $3$ tam ədəd: $N$ ( $1 \leq N \leq 200000$ 1 \leq N \leq 200\,000) — baza orqanizminin genomunun uzunluğu, $K$ ( $1 \leq K \leq 21$ 1 \leq K \leq 21) — genlərdə istifadə oluna bilən müxtəlif hərflərin sayı və $T$ ( $1 \leq T \leq 1 0^{9}$ 1 \leq T \leq 10^9) — icazə verilən maksimal xəstəlik riski verilir. İkinci sətirdə baza orqanizminin genomu verilir — uzunluğu $N$ olan sətir, yalnız ilk $K$ böyük latın hərflərindən ibarət olur. Üçüncü sətirdə $K$ tam ədəd, burada $i$ -ci ədəd $i$ -ci hərfin genomdan tam çıxarılması zamanı xəstəlik riskinin nə qədər artdığını göstərir. Növbəti $K$ sətirin hər birində $K$ tam ədəd verilir, $i$ -ci sətirin $j$ -ci sütununda $i$ -ci və $j$ -ci hərflərin yan-yana gəldiyi cütlük üçün xəstəlik riski verir. Bütün verilən ədədlər tam, qeyri-mənfi və $1 0^{9}$ 10^9-dan böyük deyil. Bütün risklər riskoqramlarla verilir. İstənilən alınacaq orqanizmin maksimal xəstəlik riskinin $2^{31}$ 2^{31}-dən kiçik olduğu zəmanətlidir.

Çıxış

Bir tam ədəd çıxışa yazın — təsvir olunan üsulla xəstəlik riski $T$ -ni aşmayan, əldə edilə bilən müxtəlif orqanizmlərin sayını.

Nümunələr

Nümunə 1