3. Stable matching with multiple internships. In the simple version of the stable matching problem analyzed in class, we assumed that each company had exactly one internship available, and that there were as many internships as students. More realistically, suppose each company wants to hire some specified number of interns, and there are more students looking for internships than the total number of available positions. As before, each company has a ranking of all students and each student has a ranking of all companies. We call an assignment of students to companies unstable if either (i) student S is assigned to company C and student S is assigned to company C, but S prefers C to C and C prefers S to S; or (ii) student S is assigned to company C and student S is not assigned to any company, but C prefers S over S. Design an algorithm to find a stable matching, and prove its correctness