_VALUES = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
}

_SUBTRACTIVE = {("I", "V"), ("I", "X"), ("X", "L"), ("X", "C"), ("C", "D"), ("C", "M")}

_INT_TO_ROMAN_PAIRS = (
    (1000, "M"),
    (900, "CM"),
    (500, "D"),
    (400, "CD"),
    (100, "C"),
    (90, "XC"),
    (50, "L"),
    (40, "XL"),
    (10, "X"),
    (9, "IX"),
    (5, "V"),
    (4, "IV"),
    (1, "I"),
)


def int_to_roman(n: int) -> str:
    if not isinstance(n, int) or n < 1 or n > 3999:
        raise ValueError("integer must be in range 1..3999")

    parts: list[str] = []
    remaining = n
    for value, numeral in _INT_TO_ROMAN_PAIRS:
        while remaining >= value:
            parts.append(numeral)
            remaining -= value
    return "".join(parts)


def _parse_roman_value(s: str) -> int:
    total = 0
    i = 0
    length = len(s)
    while i < length:
        current = s[i]
        if current not in _VALUES:
            raise ValueError("invalid Roman numeral")

        if i + 1 < length:
            nxt = s[i + 1]
            if nxt not in _VALUES:
                raise ValueError("invalid Roman numeral")
            if _VALUES[current] < _VALUES[nxt]:
                pair = (current, nxt)
                if pair not in _SUBTRACTIVE:
                    raise ValueError("invalid Roman numeral")
                if current in "VLD":
                    raise ValueError("invalid Roman numeral")
                total += _VALUES[nxt] - _VALUES[current]
                i += 2
                continue

        if current in "VLD":
            if i + 1 < length and s[i + 1] == current:
                raise ValueError("invalid Roman numeral")

        if current == "I":
            j = i
            while j < length and s[j] == "I":
                j += 1
            if j - i > 3:
                raise ValueError("invalid Roman numeral")
        elif current == "X":
            j = i
            while j < length and s[j] == "X":
                j += 1
            if j - i > 3:
                raise ValueError("invalid Roman numeral")
        elif current == "C":
            j = i
            while j < length and s[j] == "C":
                j += 1
            if j - i > 3:
                raise ValueError("invalid Roman numeral")
        elif current == "M":
            j = i
            while j < length and s[j] == "M":
                j += 1
            if j - i > 3:
                raise ValueError("invalid Roman numeral")

        total += _VALUES[current]
        i += 1

    return total


def roman_to_int(s: str) -> int:
    if not s:
        raise ValueError("invalid Roman numeral")

    value = _parse_roman_value(s)
    if value < 1 or value > 3999:
        raise ValueError("invalid Roman numeral")

    if int_to_roman(value) != s:
        raise ValueError("invalid Roman numeral")

    return value