Pracsiu Dan (dnprx) Gimi a găsit un nou joc, faimos pentru dificultatea sa ridicată. Jocul este alcătuit din N camere, numerotate de la 1 la N. Fiecare cameră i conține un monstru a cărui putere este un număr natural P[i]. Gimi trece, în ordine, prin toate camerele. În fiecare cameră el poate alege să se lupte cu monstrul sau nu.
Gimi pornește cu o sabie de durabilitate S. El învinge un monstru doar dacă puterea acestuia este mai mică sau egală cu durabilitatea sabiei. După luptă, durabilitatea sabiei scade cu puterea monstrului. De exemplu, dacă Gimi are o sabie de durabilitate 10 și se luptă cu un monstru de putere 4, atunci durabilitatea sabiei sale va scădea la 6.
Ținând la reputația sa, Gimi dorește să se lupte cu exact 3 monștri din ce în ce mai puternici. Cu alte cuvinte, dacă Gimi a învins un monstru de putere x, el se va lupta în continuare numai cu monștri de putere strict mai mare decât x.
Cerința
Gimi se întreabă în câte moduri poate să aleagă 3 monștri cu care să se lupte. Două mulțimi de trei monștri se consideră diferite dacă există cel puțin un monstru în prima mulțime care nu aparține celei de-a doua mulțimi. Formal, se cere numărul de tripleți i < j < k pentru care P[i] < P[j] < P[k] și P[i] + P[j] + P[k] ≤ S.
Date de intrare
Fișierul de intrare bossfight.in conține pe prima linie două numere naturale N și S, reprezentând numărul de camere ale jocului și durabilitatea inițială a sabiei lui Gimi, iar pe a doua linie N numere naturale P[i] separate prin câte un spațiu, reprezentând puterile celor N monștri.
Date de ieșire
Fișierul de ieșire bossfight.out va conține un singur număr ce reprezintă numărul total de moduri în care Gimi poate alege monștrii.
Restricții și precizări
1 ≤ N ≤ 10.0001 ≤ P[i], S ≤ 1.000.000.000, pentru oricare1 ≤ i ≤ N- Pentru 11 puncte,
1 ≤ N ≤ 100 - Pentru 27 puncte,
1 ≤ N ≤ 2.000 - Pentru 62 puncte, fără restricții
Exemplul 1:
bossfight.in
5 9 1 2 3 4 3
bossfight.out
5
Explicație
Tripletele de poziții sunt: (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (2, 3, 4). Un exemplu de triplet incorect este (1, 4, 5), deoarece puterea monstrului din camera 4 este mai mare decât puterea monstrului din camera 5.
Exemplul 2:
bossfight.in
8 16 4 2 1 6 5 7 9 8
bossfight.out
13
Explicație
Tripletele de poziții sunt: (1, 5, 6), (2, 4, 6), (2, 4, 8), (2, 5, 6), (2, 5, 7), (2, 5, 8), (3, 4, 6), (3, 4, 7), (3, 4, 8), (3, 5, 6), (3, 5, 7), (3, 5, 8), (3, 6, 8).