Условие

---

CODE@BURGAS 2024, ГРУПА A, ЗАДАЧА B. ЛЕСОВЪДСТВО
---
Наскоро Пешо Пингвина наследи голямо количество горски площи в една "магическа гора" насред природен парк "Тратонзос". За негово съжаление през годините (поради лошо стопанство) множество бракониери са изсекли дърветата в площите и това води до намаление на магическата енергия в околността, увеличение на наводненията, намаление на количеството дивеч и т.н.
Като отговорен стопанин Пешо е решил да възстанови гората и за тази цел се е сдобил с магически кондор, който може да носи и разпръсква семена на дървета докато лети над площите. Въпреки силната магия, кондорът може да носи само определено количество семена C за време T. 
Понеже е велик магьосник, Пешо е нанесъл площите си в магическа карта, като за всяка площ е измерил нужното количество семена за да я залеси - C[i] и нужното време - T[i], за което кондорът може да облети цялата площ.
В допълнение Пешо е измерил какво време е нужно на кондорът да прелети между близките помежду си площи. С цел улеснение е нанесъл тази информация под формата на редове от вида a[i] b[i] t[i], където t[i] е времето за прелитане между a[i] и b[i]. Времето за прелитане между b[i] и a[i] е също t[i].
Презареждането на кондора със семена е трудоемко занимание и заради това Пешо иска от вас да му помогнете да пресметне какъв е минималният брой зареждания, с които може да залеси всички площи.

Ограничения:
5 <= N <= 20 -  броят на площите за залесяване
5 <= M <= 200 - броят на възможните прелитания между дадени две площи
5 <= C <= 400 - капацитетът на кондора
5 <= T <= 400 - времето, за което кондорът може да лети без презареждане
5 <= C[i] <= C - капацитетът на площ i
5 <= Т[i] <= T - времето за облитане на площ i
1 <= a[i] <= N
1 <= b[i] <= N
1 <= t[i] <= T - времето за прелитане между a[i] и b[i]

Примерен вход:
5 8 30 40
10 20
20 30
15 14
30 15
10 30
1 2 10
2 3 40
1 3 1
1 5 10
2 5 15
4 5 4
4 3 1
2 4 5

Примерен изход:
3

Обяснение:
На първия ред на стандартния вход се подават четири числа N, М, C и T.
Следват N реда от вида C[i], T[i], които описват капацитета и времето за облитане на площите. 
Следват М реда от вида a[i], b[i], t[i], номера на две площи (по ред на задаване на стандартния вход) и времето нужно за прелитане между тях..
На стандартния изход трябва да изпринтирате едно число - минималният брой зареждания на кондора, така че да залеси всички площи.
Кондорът не може да залесява частично (целият капацитет на площта трябва да бъде използван).