Let's say there is a flight and some passengers want to book seats in it. Some passenger have seat preference while some can adjust on any seat. For ex: let's say there can be 4 passengers with seat preferences W(window), M(middle), W(window), and A(Any) respectively.

The structure of the flight is given below:

• A B C D E F
• . . . . . .
• . . . . . .
• . . . . . .

• A and F : Window seats

• B and E : Middle seats
• C and D: Aisle seats

Every seat has some cost associated with it and some seats are already booked (they cannot be purchased). Now, we need to assign seats to the passengers such that they are as close as possible and total cost is minimized.

Maximum passengers is upto 10 and there can be 30 rows of seats at max.

Please help me with coming up a good approach to solve this problem.