Problem E

Adventure Travel

A tour company is planning adventure day trips to a small island. Every morning, a boat will take a group of people to the dock on the west side of the island. People can take different routes across the island, doing different activities along the way. Due to equipment and/or time constraints, there is a maximum number of people that can do each activity per day. The final activities will finish at the dock on the east side of the island, where a boat will take everyone back to the mainland in the evening.

A map of the island is given below. Nine different locations on the island are marked with the letters \(A\) through \(H\) and \(J\), where \(A\) marks the dock on the west side and \(J\) marks the dock on the east side. Arrows, each labelled with a travel activity and a maximum number of people, indicate how people can move between locations on their way from \(A\) to \(J\).

What is the maximum number of people that can travel from \(A\) to \(J\) in one day using only the routes and activities shown?

This problem was inspired by a past Beaver Computing Challenge (BCC) problem.