C. Хувиргалт

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

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

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

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

Олимпиа гаригийн эрдэмтэд балар эртний үеийн бие махбодын хувиргалтын талаарх нэгэн туршилтыг явуулж байв. Уг гаригийн бие махбодын женом нь Англи цагаан толгойн эхний $K$ ширхэг том үсгүүдээс тогтох тэмдэгт мөрөөр дүрслэгдэх ажээ. Женом гэдэг нь амьд махбодын генетикийн материал эд гэж үзэж болох бөгөөд энэ нь генүүдээс тогтох юм. Төрөл бүрийн генүүдийн хос болгоны хувьд тэд $a_{i, j}$ гэсэн утгыг тодорхойлсон байх бөгөөд уг утга нь женом дотор эдгээр төрлийн генүүд нь зэрэгцэн орсон тохиолдолд бие махбодын өвчлөх эрсдэлийг тооцсон утга юм (энд $i$ нь эхний генийн дугаарыг, $j$ нь 2-дахь генийн дугаарыг илэрхийлнэ). 'A' ген нь 1 дугаартай, 'B' ген нь 2 дугаартай гэх мэтчилэн дугаарлагдсан байна. Жишээлбэл $a_{3, 2}$ гэдэг нь 'CB' гэсэн хэсгийн эрсдэлийг илэрхийлнэ. Бие махбодын өвчлөх нийт эрсдэл нь тухайн бие махбодын женом доторх зэргэлдээ орших хос генүүд болгоны эрсдэлүүдийн нийлбэртэй тэнцүү байх юм.

Эрдэмтэд аль хэдийн үндсэн бие махбодыг гарган авсан байв. Уг бие махбодыг хувиргах замаар шинэ бие махбодыг гарган авч болно. Хувиргалт нь ямар нэгэн төрлүүдийн бүх генүүдийг устгах замаар хийгдэх боловч ингэснээр тухайн бие махбодын өвчлөх эрсдэл нь тодорхой хэмжээгээр нэмэгдэж байх юм. Өөрөөр хэлбэл төрөл бүрийн генүүдийн хувьд эрдэмтэд $t_{i}$ гэсэн утгыг тодорхойлсон байх бөгөөд энэ нь $i$-р төрлийн бүх генүүд нь женомоос устгагдсан тохиолдолд тухайн бие махбодын өвчлөх нийт эрсдэл дээр нэмэгдэх утгыг илэрхийлнэ. Жишээлбэл $t_{4}$ гэдэг нь женомоос бүх 'D' гэсэн генүүд нь устгагдсан тохиолдолд бие махбодын өвчлөх нийт эрсдэл дээр нэмэгдэх утгыг илэрхийлнэ.

Эрдэмтэд өгөгдсөн бие махбодоос хувиргах замаар гарган авах, бие махбодын өвчлөх нийт эрсдэл нь $T$-ээс ихгүй байх ялгаатай бие махбодуудын тоог мэдэхийг хүсжээ. Тэд зөвхөн дээр дүрслэгдсэн хувиргах аргыг ашиглаж болно гэж үзнэ үү. Хэрэв 2 бие махбодын женомуудыг илэрхийлэх тэмдэгт мөрүүд нь ялгаатай байвал эдгээр 2 бие махбодуудыг ялгаатай гэж үзнэ. Мөн женом нь дор хаяж нэг ширхэг ген агуулсан байна.

Оролт

Оролтын эхний мөрөнд 3-н бүхэл тоо $N$ ($1 ≤ N ≤ 200 000$) -- үндсэн бие махбодын женомын урт, $K$ ($1 ≤ K ≤ 22$) -- женом дотор байж болох хамгийн олон генийн төрлийн тоо болон $T$ ($1 ≤ T ≤ 2*10^{9}$) -- зөвшөөрөгдсөн хамгийн их өвчлөх эрсдэлийн утга өгөгдөнө. 2-дахь мөрөнд өгөгдсөн бие махбодын женом өгөгдөнө. Энэ нь Англи цагаан толгой эхний $K$ ширхэг том үсгүүдээс тогтох $N$ урттай тэмдэгт мөр байна.

3-дахь мөрөнд $K$ ширхэг тоо $t_{1}, t_{2}, ..., t_{K}$-ууд өгөгдөх ба энд $t_{i}$ нь $i$-р төрлийн бүх генүүд нь женомоос устгагдсан тохиолдолд тухайн бие махбодын өвчлөх нийт эрсдэл дээр нэмэгдэх утгыг илэрхийлнэ.

Дараагийн $K$ ширхэг мөрөнд өгөгдсөн матрицын элементүүд $a_{i, j}$-ууд өгөгдөнө. $i$-р мөр нь $K$ ширхэг тоо агуулсан байна. $i$-р мөрийн $j$-р тоо нь эхний ген нь $i$-р том үсэг (Англи цагаан толгойн дарааллаар) байх, 2-дахь ген нь $j$-р том үсэг (Англи цагаан толгойн дарааллаар) байх хос генүүдийн өвчлөх эрсдэлийн утгыг ($a_{i, j}$) илэрхийлнэ. Түүнчлэн уг өгөгдсөн матриц нь заавал тэгш хэмтэй байх албагүй юм.

Оролтод өгөгдөх бүх тоонууд нь сөрөг биш бүхэл тоонууд байх бөгөөд $T$--ээс бусад бүх тоонууд нь $10^{9}$-ээс хэтрэхгүй байна. Мөн үндсэн бие махбодоос хувиргах замаар гарган авч болох бие махбодын боломжит хамгийн их өвчлөх нийт эрсдэл нь $2^{31}$-ээс эрс бага байна.

Гаралт

Өвчлөх нийт эрсдэл нь $T$-ээс ихгүй байх үндсэн бие махбодоос хувиргах замаар гарган авч болох ялгаатай бие махбодуудын тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
5 3 13
BACAC
4 1 2
1 2 3
2 3 4
3 4 10
Гаралт
5

Тэмдэглэл

Тайлбар: та жишээнд өгөгдсөн бодлогын хувьд дараах бие махбодуудыг гарган авч болно (хаалтан дотор өвчлөх нийт эрсдэлүүдийг бичив): BACAC (11), ACAC (10), BAA (5), B (6), AA (4).

Орчуулагчийн тайлбар: Хэрэв А болон В гэсэн төрлийн генүүдийг устган СС гэсэн женомтой бие махбодыг гарган авсан тохиолдолд өвчлөх нийт эрсдэл нь 10+4+1=15 болж $T$-ээс их байгааг анхаарна уу.

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