from collections import Counter

def pairs(d):
    def pairname(a,b):
        a,b = sorted([a,b])
        return f"{a}/{b}"
    assert len(d) >= 2

    result = Counter()

    #reduce N>3 cases to an N==3 or N==2 case
    while len(d) > 3:
        #convert to sortable mutable collection
        seq = [[v,k] for k,v in d.items()]

        #eliminate smallest department by pairing it with largest department
        while seq[0][0] > 0:
            seq = sorted(seq)
            seq[0][0] -= 1
            seq[-1][0] -= 1
            result[pairname(seq[0][1], seq[-1][1])] +=1

        #convert back to dict, omitting any departments with no unpaired people
        d = {k:v for v,k in seq if v>0}
    if len(d) == 3:
        a,b,c = d.values()
        x,y,z = d.keys()
        if a+b < c or a+c < b or b+c < a:
            raise Exception("No solution")
        result[pairname(x,y)] += (+a+b-c)//2
        result[pairname(x,z)] += (+a-b+c)//2
        result[pairname(y,z)] += (-a+b+c)//2
    elif len(d) == 2:
        a,b = d.values()
        x,y = d.keys()
        if x != y:
            raise Exception("No solution")
        result[pairname(x,y)] += a
    elif len(d) == 1:
        raise Exception("No solution")

    return dict(result)


data = {"HR":10, "R&D":95, "Admin":99, "Mgmt": 50, "Sales": 77}
print("input: ", data)
print("output:", pairs(data))