Une entreprise teste une technologie de production d'antimatière utilisée comme carburant dans un vaisseau interplanétaire. L'antimatière est produite par des expériences spéciales réalisées dans un réacteur.

On connaît $n$ types d'expériences permettant de produire de l'antimatière. Une expérience de type $i$ ajoute entre $l_i$ et $r_i$ grammes d'antimatière dans le conteneur de sortie du réacteur. Pour des raisons de sécurité, il est interdit d'accumuler plus de $a$ grammes d'antimatière dans ce conteneur.

Le coût d'une expérience de type $i$ est $c_i$, et un gramme de l'antimatière produite vaut $10^9$.

Si les expériences ont produit $t$ grammes d'antimatière dans le conteneur et que leur coût total est $s$, le bénéfice est défini par la formule $(t\cdot 10^9-s)$. L'entreprise doit élaborer une stratégie d'expérimentation qui maximise le bénéfice qu'elle peut obtenir de manière garantie.

En fonction des résultats des expériences précédentes, la stratégie détermine le type de la prochaine expérience ou décide d'arrêter les expériences. Une stratégie garantit un bénéfice de $x$ si, quels que soient les résultats des expériences, d'une part le conteneur du réacteur contient au plus $a$ grammes d'antimatière, et d'autre part le bénéfice est d'au moins $x$.

Par exemple, supposons qu'il n'existe qu'un seul type d'expérience, produisant entre $4$ et $6$ grammes d'antimatière, que son coût soit de $10$ et que la capacité du conteneur soit de $17$ grammes. Après deux expériences, le conteneur peut contenir entre $8$ et $12$ grammes d'antimatière. Si l'on a obtenu $12$ grammes, aucune nouvelle expérience n'est possible : une production de $6$ grammes pourrait faire déborder le conteneur. Dans les autres cas, on peut réaliser l'expérience une troisième fois et obtenir entre $12$ et $17$ grammes d'antimatière. Dans le pire cas, il faudra réaliser trois expériences, pour un coût total de $30$, et le bénéfice sera $(12\cdot 10^9-30)=11\,999\,999\,970$.

Écrivez un programme qui détermine le bénéfice maximal $x$ que l'on peut obtenir de manière garantie.

Entrée

La première ligne contient deux entiers : $n$, le nombre de types d'expériences, et $a$, la quantité maximale d'antimatière autorisée dans le conteneur ($1\le n\le 100$, $1\le a\le 2\,000\,000$).

Les $n$ lignes suivantes contiennent chacune trois entiers $l_i$, $r_i$ et $c_i$ : respectivement la quantité minimale et maximale d'antimatière produite par une expérience de type $i$, et le coût d'une telle expérience ($1\le l_i\le r_i\le a$, $1\le c_i\le 100$).

Sortie

La sortie doit contenir un entier : le bénéfice maximal $x$ que l'on peut obtenir de manière garantie.

Exemples

Entrée 1

1 17
4 6 10

Sortie 1

11999999970

Entrée 2

2 11
2 2 100
3 5 5

Sortie 2

9999999890

Sous-tâches