# Problem 4. (10 points)

On December 31 at 16:35, Misha realized he had no New Year's gifts for his entire family. He wants to give different gifts to his mother, father, brother, and sister. Each of the gifts is available in 4 stores: Romashka, Odynachik, Nezabudka, and Lysichka, which close at 20:00. The journey from home to each store and between any two stores takes 30 minutes.

The table below shows the cost of the gifts in all four stores and the time Misha will need to spend shopping in each store. What is the minimum amount of money Misha can spend if he must definitely manage to buy all 4 gifts?

|  | mother | father | brother | sister | Time spent in the store (min.) |
| :--- | :--- | :--- | :--- | :--- | :--- |
| Romashka | 1000 | 750 | 930 | 850 | 35 |
| Odynachik | 1050 | 790 | 910 | 800 | 30 |


| Nezabudka | 980 | 810 | 925 | 815 | 40 |
| :--- | :--- | :--- | :--- | :--- | :--- |
| Lysichka | 1100 | 755 | 900 | 820 | 25 |
# Solution:

Notice that in each of the stores, there is a "unique" gift with the lowest price.

If Misha managed to visit all 4 stores, he would spend the minimum amount of $980+750+900+800=3430$ rubles. However, visiting any three stores would take Misha at least $30 * 3+25+30+35=180$ minutes. Considering the additional 30 minutes to travel to the fourth store, he would not make it. On the other hand, Misha can manage to visit any three out of the four stores—along with the travel time, he would arrive at the third store no later than $3 * 30+35+40=165$ minutes, i.e., at $19:10$.

Then, in one of the stores, he needs to choose 2 gifts to minimize the extra cost. Let's create a table of the extra costs:

|  | mom | dad | brother | sister |
| :--- | :--- | :--- | :--- | :--- |
| Daisy | 20 | 0 | 30 | 50 |
| Dandelion | 70 | 40 | 10 | 0 |
| Forget-me-not | 0 | 60 | 25 | 15 |
| Lily of the Valley | 120 | 5 | 0 | 20 |

From the table, it is easy to see that the minimum extra cost is 5 rubles at the "Lily of the Valley" store for the gift for dad.

Therefore, Misha goes to Dandelion, Forget-me-not, and Lily of the Valley, and the total cost for the gifts will be $3430+5=3435$ rubles.

Answer: 3435 rubles.

Criteria:

Correct answer - 2 points

Reasoning that he cannot visit all 4 stores - 2 points

Reasoning that he can visit any 3 stores - 2 points

Explanation that the minimum extra cost is 5 rubles - 4 points

#