162. Roman to Integer

Given a roman numeral string s, convert it to an integer.

Roman numeral symbols and their values:
I=1, V=5, X=10, L=50, C=100, D=500, M=1000.

Subtractive notation: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900.

The input is guaranteed to be in the range [1, 3999].

Input: A string s representing a valid roman numeral.

Output: An integer — the decimal value of the roman numeral.

Examples

Input: III
Output: 3
Explanation: III = 1 + 1 + 1 = 3.

Input: LVIII
Output: 58
Explanation: L=50, V=5, III=3 → 58.

Input: MCMXCIV
Output: 1994
Explanation: M=1000, CM=900, XC=90, IV=4 → 1994.

Constraints

• 1 <= s.length <= 15
• s contains only characters: I, V, X, L, C, D, M
• It is guaranteed that s is a valid roman numeral in the range [1, 3999]

Asked by