Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

| Symbol | Value |

|--------|-------|

| I | 1 |

| V | 5 |

| X | 10 |

| L | 50 |

| C | 100 |

| D | 500 |

| M | 1000 |

When a smaller value precedes a larger value, it is subtracted (e.g., IV = 4, IX = 9). Given a Roman numeral string s, convert it to an integer.

Example 1:

Input: III
Output: 3

Example 2:

Input: LVIII
Output: 58

Example 3:

Input: MCMXCIV
Output: 1994

Constraints:

• 1 ≤ s.length ≤ 15
• s contains only valid Roman numeral characters
• 1 ≤ answer ≤ 3999

Input format: A single Roman numeral string.

Output format: Integer value.