Ральф идет в Грибной лес собирать грибы.
В Грибном лесу m ориентированных дорожек, соединяющих n деревьев. На каждой дорожке растут грибы. Когда Ральф проходит по дорожке, он собирает все грибы на этой дорожке. Однако, в Грибном лесу такая плодородная почва, что грибы растут с фантастической скоростью. Новые грибы вырастают, как только Ральф заканчивает собирать грибы на дорожке. А именно, после того, как Ральф проходит по дорожке в i-й раз, вырастает на i грибов меньше, чем было до этого прохода. Таким образом, если на дорожке изначально было x грибов, то Ральф соберет x грибов в первый проход, x - 1 гриб во второй, x - 1 - 2 гриба в третий и так далее. Однако, количество грибов не может стать меньше 0.
Например, пусть изначально на дорожке росло 9 грибов. Тогда количество грибов, которое соберет Ральф, равно 9, 8, 6 и 3 для проходов с первого по четвертый. Начиная с пятого прохода и далее Ральф ничего не сможет собрать с этой дорожки (но все еще может по ней ходить).
Ральф решил начать от дерева s. Какое максимальное количество грибов он может собрать, передвигаясь только по описанным дорожкам?
Примечание
В первом примере Ральф может три раза пройти по кругу и собрать 4 + 4 + 3 + 3 + 1 + 1 = 16 грибов. После этого не будет грибов, которые Ральф может собрать.
Во втором примере Ральф может пойти к дереву 3 и собрать 8 грибов на дорожке от дерева 1 до дерева 3.