class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """

        res = ''
        dict = {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'}

        item = dict.items()
        item.sort()
        for key, val in reversed(item):
            while num >= key:
                num -= key
                res += val
        return res

if __name__ == '__main__':
    so = Solution()
    so.intToRoman(4)