Roman numerals

Roman numerals are based on seven symbols: "I", "V", "X", "L", "C", "D" and "M". The values of these symbols are $1$, $5$, $10$, $50$, $100$, $500$, and $1000$, respectively. To calculate the decimal value of a Roman numeral, use the following algorithm:

1. Find the most significant ("most valuable") symbol. If there are multiple such symbols, choose the leftmost one. Let this symbol be at position i.

2. Denote as Middle the value of the symbol at position i.

3. Calculate the value of the Roman numeral formed by the symbols to the right of i. Denote this value as Right.

4. Calculate the value of the Roman numeral formed by the symbols to the left of i. Denote this value as Left.

5. The value of the Roman numeral is Middle + Right – Left. It is clear that, using this algorithm, the same number can be written in many ways. For example, the number $19$ can be written as "IXX", "XIX", "XVIV", "XVIIII", and so on.

Given a decimal number $n$ and a Roman numeral $S$, find such a permutation of the symbols in $S$ that represents $n$ in Roman notation.