Given a string S representing a roman numeral. Convert S into integer.

Problem Note

• S is guaranteed to be within the range from 1 to 3999.
• Roman numerals are represented by seven different symbools :
``````SYMBOL       VALUE
I             1
V             5
X             10
L             50
C             100
D             500
M             1000    ``````
• For example, two is written as `II` in Roman numeral, just two one's added together. Twelve is written as, `XII`, which is simply `X` + `II`. The number twenty seven is written as `XXVII`, which is `XX` + `V` + `II`.
• Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five, so we subtract one from five to make it four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:
1. I can be placed before V (5) and X (10) to make 4 and 9.
2. X can be placed before L (50) and C (100) to make 40 and 90.
3. C can be placed before D (500) and M (1000) to make 400 and 900.

Example 1

``````Input: "III"
Output: 3``````

Example 2

``````Input: "IV"
Output: 4 ``````

Example 3

``````Input: "IX"
Output: 9``````

Example 4

``````Input: "LVII"
Output: 57
Explanation: L = 50, V= 5, II = 2.``````