Дан неориентированный граф без петель и кратных ребер. Вершины графа бывают двух типов - черные и белые. Если черная вершина не имеет ни одной соседней белой, то она сразу же исчезает. Аналогично, если белая вершина не имеет черных соседей, то она тоже пропадает. Для каждой вершины известна стоимость ее удаления. Определить минимальную стоимость удаления всех вершин.

Входные данные

Два числа n и k (1 ≤ n ≤ 100, 0 ≤ k ≤ n · (n - 1) / 2) - количество вершин и ребер в графе. Заием следуют n строк по два числа в каждой t, c (1 ≤ c ≤ 106) - тип вершины (0 - белая, 1 - черная) и стоимость ее удаления. Затем идут k строк по два числа в каждой - a, b (1 ≤ a, b ≤ n) - номера вершин, соединенных ребром.

Выходные данные

Вывести минимальную стоимость удаления всех вершин.