USACO 2019 - Dec - Gold - Moortal Cowmbat

Xem dạng PDF

Gửi bài giải

Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
http://www.usaco.org/index.php?page=viewproblem2&cpid=971
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bessie đã chơi trò chơi đối kháng Moortal Cowmbat trong một thời gian dài. Tuy nhiên gần đây, những nhà phát triển trò chơi đã thực hiện một cập nhật mới khiến cho Bessie phải thay đổi phong cách chơi của bạn ấy.

Trò chơi sử dụng ~M~ nút bấm là ~M~ chữ cái in thường đầu tiên trong bảng chữ cái Latin. Combo yêu thích của Bessie được biểu diễn dưới dạng một xâu các nút bấm ~S~, độ dài ~N~. Tuy nhiên theo như cập nhật mới nhất của trò chơi, nếu mỗi nút bấm được thực hiện, nó phải nằm trong một nhóm chứa ít nhất ~K~ nút bấm liên tiếp giống nó. Bessie muốn thay đổi combo của bạn ấy sao cho phù hợp với yêu cầu mới của trò chơi.

Bessie mất ~a_{ij}~ ngày để luyện tập khả năng bấm nút từ kí tự ~i~ sang ~j~ tại một vị trí bấm nút ~i~ trong xâu ~S~. Hãy giúp Bessie tìm ra số ngày ít nhất để bạn ấy có thể chơi trò chơi yêu thích của mình.

Input

  • Dòng đầu tiên ghi các số nguyên dương ~N~, ~M~, ~K~ ~(1 \le K \le N \le 100000, 1 \le M \le 26)~.

  • Dòng thứ hai chứa xâu ~S~ ban đầu.

  • ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ~M~ số ~a_{i1}...a_{iM}~ thể hiện số ngày thay đổi kí tự từ ~i~ sang kí tự ~j~. ~(0 \le a_{ij} \le 1000)~.

Output

  • In ra số ngày biến đổi ít nhất để xâu ~S~ hợp lệ.

Sample Input

5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 0

Sample Output

5

Note

  • Giải thích: thay đổi ~a~ thành ~b~, ~d~ thành ~e~, sau đó cả 2 kí tự ~e~ thành ~c~.

  • Các tests 2-4 thoả mãn ~N \le 1000, K \le 50~.

  • Các tests 5-8 thoả mãn ~N \le 30000, K \le 50~.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 2
    ThuyLinhNg  đã bình luận lúc 21, Tháng 9, 2021, 2:38

    một nhóm chứa ít nhất K nút bấm giống nó

    Nên đổi thành

    một nhóm các nút bấm liên tiếp chứa ít nhất K nút bấm giống nó

    Cho rõ ạ.


    • 3
      hieplpvip  đã bình luận lúc 21, Tháng 9, 2021, 4:03

      Mình đã cập nhật. Cảm ơn bạn đã report. Lần tới bạn có thể sử dụng tính năng "Báo cáo vấn đề" để admin dễ theo dõi hơn.