주유소

유가가 폭락하자 펭귄 Pengu는 D킬로미터 떨어진 곳에 사는 쥐 Squeaky를 만나러 가기로 했다.

Pengu의 펭귄모빌은 F리터의 연료를 가지고 출발하고, 1킬로미터를 이동할 때마다 연료 1리터를 소비하며, 어느 시점에서든 원하는 만큼의 연료를 담을 수 있다.

또한 Pengu의 집과 목적지 사이에는 N개의 주유소가 있고, i번째 주유소는 Pengu의 집에서 Xi킬로미터 떨어진 곳에 있다. 각 주유소에서 Pengu는 Ai리터만큼만 연료를 넣을 수 있으며(값싼 연료를 사재기하는 운전자를 막기 위한 제한이다), F ≤ Bi일 때만 연료를 넣을 수 있다(연료가 가장 필요한 운전자에게 연료가 돌아가도록 하기 위해서다). 여기서 F는 Pengu가 출발할 때 가지고 있던 연료의 양(리터)이다.

효율적인 펭귄인 Pengu는 목적지에 도달할 수 있으면서도 F의 값을 최소화하고 싶어 한다.

프로그램은 표준 입력에서 입력을 읽어야 한다. 첫 번째 줄에는 두 정수 N과 D가 주어진다. 이어서 N개의 줄이 주어진다. i번째 줄에는 세 정수 Xi, Ai, Bi가 주어지며, 이는 i번째 주유소를 나타낸다.

프로그램은 표준 출력으로 출력을 해야 한다. 목적지에 도달하는 데 필요한 F의 최솟값을 한 줄에 정수 하나로 출력한다.

• 1 ≤ N ≤ 3 × 105
• 1 ≤ Ai, Bi, D ≤ 109
• 0 < Xi < D