축제 바오바브

Math&Mech 건물에서 바오바브가 어디 있는지 아는가? 모른다면, 대회가 끝난 뒤에 아는 사람에게 물어보라...

바오바브가 나무라는 것은 누구나 안다. 그래서 다른 나무처럼 줄기와 가지가 있다. 가지는 줄기나 다른 가지에서 자란다.

9월 1일이 되면 새로 온 학생들이 편안함을 느끼도록 이 바오바브를 보통 장식한다. 이를 위해 건물 지하 깊은 곳에 작고 알록달록한 장식품이 담긴 큰 상자가 있다. 모든 장식품의 무게는 정확히 1그램이다.

안타깝게도 바오바브는 매우 늙어서, 장식품으로 과부하가 걸리면 부러진다. 각 가지마다 장식품을 실을 수 있는 최대 무게가 주어진다. 어떤 가지가, 그 가지에서 (직접 또는 다른 가지를 거쳐) 자라난 모든 가지와 함께 실은 장식품의 총 무게가 이 한도를 넘으면 그 가지는 부러진다. 이는 용납할 수 없다. 하지만 어떤 가지가 부러지지 않는다면, 한 가지에 장식품 여러 개를 달 수 있다.

어떤 가지는 입구 근처에 있어 잘 보이고, 어떤 가지는 바오바브 깊숙한 곳에 숨어 있다. 그래서 장식품마다 위치에 따라 더 많거나 적은 기쁨을 준다. 바오바브의 총 기쁨은 장식품이 달린 가지들의 기쁨의 합이다. 한 가지에 장식품이 여러 개 있으면, 그 가지의 기쁨은 개수만큼 곱해진다.

바오바브가 얻을 수 있는 최대 총 기쁨은 얼마인가?

첫째 줄에 두 정수 $n$과 $t$가 주어진다. $n$은 바오바브의 가지 수, $t$는 장식품의 수이다 ($1 \le n \le 100\,000$, $1 \le t \le 10^9$). 다음 $n$개의 줄에는 각각 세 정수 $d_i$, $p_i$, $w_i$가 주어진다. $d_i$는 $i$번째 가지에 장식품 하나를 달았을 때 주는 기쁨, $p_i$는 $i$번째 가지가 자라난 가지(또는 $i$번째 가지가 줄기에서 직접 자라난 경우 $0$), $w_i$는 $i$번째 가지가 실을 수 있는 장식품의 최대 무게이다 ($1 \le d_i, w_i \le 10^9$, $0 \le p_i \le n$).

모든 가지는 줄기에서 직접 또는 다른 가지를 거쳐 자라난다. 또한 모든 장식품을 사용하는 것이 가능하다.

장식된 바오바브가 주는 최대 총 기쁨을 정수 하나로 출력한다.