Условие

---

CODE@BURGAS 2026, ГРУПА A, ЗАДАЧА B. МАГИЧЕСКО ПЛАНИРАНЕ
---
Наскоро Пешо Пингвина наследи големи горски площи в магическа гора. За да възстанови магията, той използва кондор, който разпръсква семена върху площите. Кондорът има ограничен капацитет от семена C и може да лети максимум време T без презареждане. Всяка площ i изисква C[i] семена и време T[i] за обработка. Между площите има прелети. Всеки прелет a, b има време t и може да се извършва само при определени периоди. Всеки прелет е разрешен само ако текущото време mod K е в интервала [L, R]. Кондорът започва от площ 1. При презареждане той се връща обратно там. Кондорът трябва да обработи всяка площ наведнъж (без частична обработка). 

Задача:
Да се намери минималният брой презареждания, така че всички площи да бъдат обработени. 

Ограничения:
5 ≤ N ≤ 18 
5 ≤ M ≤ 200 
5 ≤ C ≤ 400 
5 ≤ T ≤ 400 
1 ≤ K ≤ 50 
1 ≤ C[i] ≤ C 
1 ≤ T[i] ≤ T 

Вход: 
На първия ред са записани пет цели числа: N - броят на площите; M - броят на възможните прелитания между площите; C - максималният капацитет от семена на кондора; T - максималното време, за което кондорът може да лети без презареждане; K - периодът на цикличност на достъпността на прелитанията.
Следват N реда, по един за всяка площ, съдържащи по две цели числа: C[i] - необходимото количество семена за площ i и T[i] - времето, необходимо за обработка на площ i.
Следват M реда, описващи възможните прелитания. Всеки ред съдържа пет цели числа: a, b, t, L и R, където: a и b са номера на две площи, между които има директен прелет; t е времето за прелитане между тях; L и R задават интервал от допустими моменти за използване на този прелет.

Изход: 
На един ред на стандартния изход се отпечатва едно число, съответсващо на  минималният брой презареждания.

Примерен вход:
10 21 200 200 10
17 54
22 47
47 11
19 39
8 38
26 18
9 24
18 19
27 37
29 19
2 5 12 8 9
7 1 10 5 9
4 9 1 5 5
9 6 1 9 9
10 1 8 0 8
8 6 9 3 9
5 8 7 9 9
10 8 20 2 5
3 8 5 4 9
10 2 14 7 8
7 10 1 8 8
9 4 17 3 5
9 8 12 3 7
8 4 4 0 3
1 4 19 6 6
9 5 9 6 9
5 4 19 0 2
5 6 16 9 9
3 9 18 9 9
10 8 15 9 9
9 7 9 7 8	

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