Система железнодорожного сообщения в Токио достаточно сложна. Имеется частичная карта линий и станций, как показано на рис.1. \includegraphics{https://static.e-olymp.com/content/93/93bebe848721eeb05dd1ba1b587bc55e26fff68f.jpg} Figure 1: A sample railway network Пусть Вам следует попасть на станцию \textbf{D} со станции \textbf{A}. Путем с кратчайшим расстоянием является \textbf{A→B→D}. Однако путь с кратчайшим расстоянием не всегда является путем с минимальной стоимостью. Предположим, что линии \textbf{A-B}, \textbf{B-C} и \textbf{C-D} обслуживаются одной железнодорожной компанией, а линия \textbf{B-D} - другой. В таком случае проезд по пути \textbf{A→B→C→D} может стоить меньше чем проезд по \textbf{A→B→D}. Причина состоит в том, что стоимость проезда не пропорциональна расстоянию. Обычно чем длиннее путь следования, тем меньше проезд за единицу расстояния. Если пассажир пользуется услугами нескольких железнодорожных компаний, то стоимости проездов просто складываются. И поэтому общая стоимость проезда может быть выше, чем если бы он воспользовался услугами одной компании, выбрав более длинный путь. Вам задана железнодорожная сеть, которая принадлежит разным компаниям. Таблица стоимостей проезда (правило, по которому вычисляется стоимость проезда в зависимости от расстояния) для каждой компании задается. Вам необходимо по начальной и конечной станциям найти путь между ними с наименьшей стоимостью. \InputFile Состоит из нескольких тестов, каждый из которых имеет следующий формат. \textit{\textbf{n}}\textbf{ }\textit{\textbf{m}}\textbf{ }\textit{\textbf{c}}\textbf{ }\textit{\textbf{s}}\textbf{ }\textit{\textbf{gx}}\textbf{_1 }\textit{\textbf{y}}\textbf{_1 }\textit{\textbf{d}}\textbf{_1 }\textit{\textbf{c}}\textbf{_1...}\textit{\textbf{x_m}}\textbf{ }\textit{\textbf{y_m}}\textbf{ }\textit{\textbf{d_m}}\textbf{ }\textit{\textbf{c_mp}}\textbf{_1 ... }\textit{\textbf{p_cq}}\textbf{_\{1,1\} ... }\textit{\textbf{q}}\textbf{_\{1,p1-1\}}\textit{\textbf{r}}\textbf{_\{1,1\} ... }\textit{\textbf{r}}\textbf{_\{1,p1\}...}\textit{\textbf{q_c}}\textbf{_\{,1\} ... }\textit{\textbf{q_\{c,pc\}}}\textbf{_\{-1\}}\textit{\textbf{r_c}}\textbf{_\{,1\} ... }\textit{\textbf{r_\{c,pc\}}} Входные данные содержат только неотрицательные целые числа. Первая строка описывает размер железнодорожной сети и желаемую поездку. \textbf{n} - количество станций (\textbf{2} ≤ \textbf{n} ≤\textbf{100}). \textbf{m} - количество участков, соединяющих две станции (\textbf{0} ≤ \textbf{m} ≤ \textbf{10000}). \textbf{c} - количество железнодорожных компаний (\textbf{1}≤ \textbf{c} ≤ \textbf{20}). \textbf{s} - номер начальной станции (\textbf{1} ≤ \textbf{s} ≤ \textbf{n}). \textbf{g} - номер конечной станции (\textbf{1}≤ \textbf{g} ≤ \textbf{n}, \textbf{g} ≠ \textbf{s}). Следующие \textbf{m} строк описывают железнодорожные линии. \textbf{i}-ая линия (участок) соединяет две станции - \textbf{x_i} и \textbf{y_i}\textit{ }(\textbf{1} ≤ \textbf{x_i} ≤ \textbf{n}, \textbf{1} ≤ \textbf{y_i} ≤ \textbf{n}, \textbf{x_i} ≠ \textbf{y_i}). Движение на каждом участке разрешено в обоих направлениях. Могут существовать две и более линий, соединяющих одну и ту же пару станций. \textbf{d_i} (\textbf{1} ≤ \textbf{d_i} ≤ \textbf{200}) - длина \textbf{i}-го участка. \textbf{c_i} (\textbf{1} ≤ \textbf{c_i} ≤ \textbf{c}) - номер железнодорожной компании, которая его обслуживает. Таблица стоимостей проезда (соотношение между расстоянием и стоимостью) для каждой железнодорожной компании задается в виде линейного графика. Для компании \textbf{j} количество секций в графике задается значением \textbf{p_j}\textit{ }(\textbf{1} ≤ \textbf{p_j} ≤ \textbf{50}). \textbf{q_\{j,k\}}\textit{ }(\textbf{1} ≤ \textbf{k} ≤ \textbf{p_j-1}) равно расстоянию, которое разделяет две секции графика (\textbf{1} ≤ \textbf{q_\{j,k\}} ≤ \textbf{10000}). \textbf{r_\{j,k\}}\textit{ }(\textbf{1} ≤ \textbf{k} ≤ \textbf{p_j}) задает прирост стоимости на единицу расстояния для соответствующей секции графика (\textbf{1} ≤ \textbf{r_\{j,k\}} ≤ \textbf{100}). Пусть стоимость проезда пути длины \textbf{z} составляет \textbf{f_j}(\textbf{z}). Тогда стоимость пути \textbf{z}, удовлетворяющего неравенству \textbf{q_j_\{,k-1\}+1} ≤ \textbf{z} ≤ \textbf{q_j_\{,k\}}, вычисляется из рекуррентного соотношения \textbf{f_j}(\textbf{z}) = \textbf{f_j}(\textbf{z-1})\textbf{+r_\{j,k\}}. Считайте, что \textbf{q_j_\{,0\}} и \textbf{f_j}(\textbf{0}) равны нулю, а \textbf{q_j_\{,pj\}} равно бесконечности. Например, пусть \textbf{p_j = 3}, \textbf{q_j_\{,1\} = 3}, \textbf{q_j_\{,2\} = 6}, \textbf{r_j_\{,1\} = 10}, \textbf{r_j_\{,2\} = 5} и \textbf{r_j_\{,3\} = 3}. В таком случае таблица стоимости проезда имеет вид: \textbf{q_\{j,k\}} увеличивается монотонно по отношению к \textbf{k}. \textbf{r_\{j,k\}}\textit{ }уменьшается монотонно по отношению к \textbf{k}. Последний тест содержит пять нулей и не обрабатывается. \OutputFile Для каждого теста вывести в отдельной строке стоимость наилучшего пути (пути с наименьшей стоимостью). Если из начальной станции нельзя добраться до конечной, то вывести "\textbf{-1}". Выходные данные не должны содержать лишних символов, включая пробелы. Once a route from the start to the goal is determined, the total fare of the route is computed as follows. If two or more lines of the same railway company are used contiguously, the total distance of these lines is used to compute the fare of this section. The total fare of the route is the sum of fares of such "sections consisting of contiguous lines of the same company". Even if one uses two lines of the same company, if a line of another company is used between these two lines, the fares of sections including these two lines are computed independently. No company offers transit discount.