Does having a bunch of plaintext/ciphertext pairs help you break a ciphertext with unknown plaintext?
The known plaintext is only a useful tool for establishing that you actually found the right key if we assume a secure cipher (and mode of operation, etc.). It won't help you creating a faster than brute-force attack, as ciphers are assumed to be secure against known plaintext attacks.

So the complexity of breaking the cipher is simply still $m - 1$ (half the key space) on average, i.e. no change from normal brute forcing.