E. Ойрхон оройнууд

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ оройтой жинтэй мод байгаа. Ирмэг бүр нь сөрөг биш жинтэй. Модны замын урт гэдэг нь аль ч хоёр оройн хоорондох ирмэгийн тоо юм. Замын нийт жинд бүх оройнууд агуулагдана.

Хоёр оройндууд нь хэрэв ойрхон байгай бол эдгээрийн хоорондох замын урт нь $l$-ээс их мөн эдгээрийн хоорондох замын жин нь $w$-аас их байна. Хос $v, u$ $(v < u)$ оройнуудыг тоолно, эдгээр $v$ ба $u$ оройнууд нь ойрхон байна.

Оролт

Эхний мөрөнд гурван бүхэл $n$, $l$ ба $w$ $(1 ≤ n ≤ 10^{5}, 1 ≤ l ≤ n, 0 ≤ w ≤ 10^{9})$ тоонууд агуулагдана. Дараагийн $n - 1$ мөрөнд гурван оройны тодорхойлолт агуулагдана. $i$-р мөрөнд хоёр бүхэл $p_{i}, w_{i}$ $(1 ≤ p_{i} < (i + 1), 0 ≤ w_{i} ≤ 10^{4})$ тоонууд агуулагдах ба энэ нь $i$-р орой нь $(i + 1)$ оройтой ирмэгээр холбогдсонг $p_{i}$-р илэрхийлэх ба $w_{i}$ жинтэй.

Модны оройнуудыг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.

Гаралт

Нэг мөрөнд ойрхон хос оройнуудын тоог хэвлэнэ.

С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
4 4 6
1 3
1 4
1 3
Гаралт
4
Оролт
6 2 17
1 3
2 5
2 13
1 6
5 9
Гаралт
9
Сэтгэгдлүүдийг ачааллаж байна...