{"raw_statement":[{"iden":"statement","content":"The cows have formed a dance team, and Farmer John is their choreographer! The team's latest and greatest dance involves $N$ cows ($2 \\le N \\le 10^6$) standing in a line. Each move in the dance involves two cows, up to $K$ positions apart ($1 \\le K < N$), gracefully jumping and landing in each other's position.  \n\nThere are two types of cows in the line – Guernseys and Holsteins. As such, Farmer John has documented the dance as a sequence of **length-$N$ binary strings**, where a $0$ represents a Guernsey, a $1$ represents a Holstein, and the overall string represents how the cows are arranged in the line.  \n\nUnfortunately, Farmer Nhoj (who choreographs for a rival team) has sabotaged the dance and erased all but the first and last binary strings! With a big competition quickly approaching, Farmer John must waste no time in reconstructing the dance.  \n\nGiven these two binary strings, help Farmer John find the minimum number of moves in the dance!"},{"iden":"input","content":"The first line contains $N$ and $K$.  \n\nThe second line contains the first binary string.  \n\nThe third line contains the last binary string.  \n\nIt is guaranteed that both binary strings contain the same number of ones."},{"iden":"output","content":"The minimum number of moves in the dance."},{"iden":"note","content":"##### For Sample 1:\nOne possible dance:  \n```text\n0111 -> 1011 -> 1101 -> 1110\n```\n##### For Sample 2:\nOne possible dance:  \n```text\n11000 -> 01100 -> 00110 -> 00011\n```\n##### For Sample 3:\nOne possible dance:  \n```text\n11000 -> 10010 -> 00011\n```\n\n#### SCORING:\n- Inputs 4-5: $K=1$.\n- Inputs 6-7: Both strings have at most $8$ ones.\n- Inputs 8-15: $N\\le 5000$.\n- Inputs 16-23: No additional constraints."}],"translated_statement":null,"sample_group":[["4 1\n0111\n1110","3"],["5 2\n11000\n00011","3"],["5 4\n11000\n00011","2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}