The Pine Valley Board of Education must hire teachers for the coming school year. The types of teachers and the salaries that must be paid are given in the file P09_33.xlsx. For example, 20 teachers who are qualified to teach history and science have applied for jobs, and each of these teachers must be paid an annual salary of $21,000. Each teacher who is hired teaches the two subjects he or she is qualified to teach. Pine Valley needs to hire 35 teachers qualified to teach history, 30 teachers qualified to teach science, 40 teachers qualified to teach math, and 32 teachers qualified to teach English. The board has $1.4 million to spend on teachers’ salaries. A penalty cost of $1 is incurred for each dollar the board goes over budget.

For each teacher by which Pine Valley’s goals are unmet, the following costs are incurred (because of the lower quality of education): science, $30,000; math,

$28,000; history, $26,000; and English, $24,000.

Determine how the board can minimize its total cost due to unmet goals.