For the bonus part you may watch the tutorial in the website which explains the algorithm.
http://www.nrmp.org/match-a-to-z/video-tutorials/about-the-matching-algorithm-tutorial/

Note that the algorithm is applicant proposing. 
The preference lists do not have to contain every applicant-program.
An applicant may not be matched with any program and quoata for a program does not have to be filled.
Input format for bonus part:

Applicants/Students
n
preference list for applicant 1
preference list for applicant 2
.
.
.
preference list for applicant n
m
quota1 quota2 ... quotan
preference list for program 1
preference list for program 2
.
.
.
preference list for program m



Example:

4
2 3 1
1 3 2
1 3
3
3
1 2 2
3 4 2
3 1 4
2 1 3 4

There are 4 applicants and 3 programs. Quota of each program is 1 2 2 respectively.

Number of applicants:   4
Preference list for a1: 2 3 1
Preference list for a2: 1 3 2
Preference list for a3: 1 3
Preference list for a4: 3
Number of programs:     3
Quoata of each program: 1 2 2
Preference list for p1: 3 4 2
Preference list for p2: 3 1 4
Preference list for p3: 2 1 3 4

Output format for bonus part:

applicant1-program
applicant2-program
.
.
.
applicantn-program

example:

1-2
2-3
3-1
4-3

applicant 1 is matched to program 2
applicant 2 is matched to program 3
applicant 3 is matched to program 1
applicant 4 is matched to program 3

