Subtask 1

It suffices to output the binary character pairing ~|M|~ times.

Time Complexity: ~\mathcal{O}(|M|)~

Subtask 2

First, reverse the message and each binary string to allow for in-time backtracking.

Then, realize a DP state: DP[i][j]: the minimum number of binary strings to get to the i-th character of the message with the j-th binary string as the last message.

Now, verify that you can use each binary string for each index (i.e., the binary string and message match) and maintain the DP state.

Finally, start backtracking for the minimum length and lexicographically least message and output it.

Time Complexity: ~\mathcal{O}(|M| \sum_{i=1}^N |N_i|)~

~\sum_{i=1}^N |N_i|~ denotes the sum of the length of all the binary strings.

Note that there are faster solutions.