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 as follows:

Teacher can teach & Number applying & Annual salary History, science &20 & $21,000 History, math &15 & $22,000 English, science & 12 & $23,000 English, math & 14 & $24,000 English, history & 13 & $25,000 Science, math & 12& $26,000

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.