Excursions

Irina works in an excursion company in Saratov. Today, she is going to organize excursions in the cities of Saratov and Engels.

There are $$$n_1$$$ sights in Saratov and $$$n_2$$$ sights in Engels. The cities are separated by a river, but there are $$$m$$$ bus routes that go along the bridges and allow tourists to go from Saratov to Engels and vice versa. The $$$i$$$-th bus route goes from the $$$x_i$$$-th sight in Saratov to the $$$y_i$$$-th sight in Engels, and in the opposite direction as well.

Irina wants to plan excursions for the current day. The excursion trips start in Saratov in the morning, continue in Engels in the afternoon, and finish in Saratov in the evening.

Each tourist starts their excursion day at some sight in Saratov, $$$k_i$$$ tourists start at the $$$i$$$-th sight. Then the tour guides lead them to Engels: at each sight in Saratov, a tour guide chooses a bus route leading from this sight to Engels, and all the tourists starting from this sight transfer to Engels along this bus route. After the excursions in Engels are finished, the same thing happens: at each sight in Engels, a tour guide chooses a bus route leading from this sight to Saratov, and all the tourists at this sight transfer to Saratov along this bus route.

This process can lead to a situation such that some tourists return to the same sight in Saratov where they started in the morning. Obviously, tourists don't like it; so Irina wants to choose where the tour guides take the tourists (both on the way from Saratov to Engels and on the way from Engels to Saratov), so that the minimum possible number of tourists return to the same sight where they started. Help Irina to find an optimal plan!