#Pyth, <s>30</s> 25 bytes

    jb.eu_GkbceQs*R/*FQ4"EDMC

[Live demo and all test cases](https://pyth.herokuapp.com/?code=jb.eu_GkbceQs*R%2F*FQ4"EDMC&input=%5B8%2C3%5D&test_suite=1&test_suite_input=%5B4%2C1%5D%0A%5B4%2C4%5D%0A%5B8%2C3%5D%0A%5B20%2C5%5D&debug=1).

Cut off 5 bytes thanks to @Jakube!

Same algorithm as my K answer...but a *lot* shorter.

30-byte version:

    jb.e?%k2_bbcjkm*/*FQ4d"EDMC"hQ

[Live demo and all test cases for 50-byte version](https://pyth.herokuapp.com/?code=jb.e%3F%25k2_bbcjkm*%2F*FQ4d%22EDMC%22hQ&input=%5B8%2C3%5D&test_suite=1&test_suite_input=%5B4%2C1%5D%0A%5B4%2C4%5D%0A%5B8%2C3%5D%0A%5B20%2C5%5D&debug=1).