Макс и выбор такси: такси наносит ответный удар

Как вы помните, Макс и другие студенты, находясь в командировке, часто пользуются услугами такси. На этот раз ребята отправились в другой соседний регион, где проводится знаменитый Апрельский Чемпионат.

Университет-организатор Апрельского Чемпионата имеет N корпусов, пронумерованных от 1 до N. Корпуса соединены сетью из M дорог, проезд по i-й из которых занимает T_i минут.

Макс и его друзья поселились в гостинице, находящейся в непосредственной близости от корпуса, имеющего номер S. К сожалению, никто из ребят не запомнил, в каком именно корпусе будет проходить чемпионат, поэтому сейчас они изучают карту города и планируют, как лучше всего добраться до того или иного корпуса.

Оказалось, что в городе, в котором проводится Апрельский Чемпионат, службы такси имеют ряд особенностей:

• Во-первых, этих служб очень много (можно считать, что сколь угодно большая группа пассажиров всегда сможет заказать такси).
• Во-вторых, несмотря на большое количество служб, в каждой из них можно заказать только одну машину.
• В-третьих, водители разных служб такси не очень жалуют друг друга, и поэтому обязательно поедут к месту назначения различными путями (пути A и B считаются различными, если существует хотя бы одна дорога, входящая в путь A и не входящая в путь B или наоборот).

Макс и другие студенты долго чесали в затылках, силясь понять бесконечную мудрость местной сферы транспортного обслуживания.

Сейчас ребята хотят выяснить, сколько существует корпусов, до которых они могут добраться одновременно и за минимально возможное время, если воспользуются местными службами такси и начнут поездку одновременно. Помогите им найти ответ на этот вопрос. Помните, что во всех такси 4 места для пассажиров.