Aladdin

Trong chúng ta, hầu hết ai cũng đều nghe biết qua câu chuyện Aladdin và cây đèn thần. Sau khi vượt qua bao thử thách Aladdin được thần đèn tặng cho rất nhiều cổ vật. Thần đèn bày ra trước mặt Aladdin $n$ cổ vật được, các cổ vật này được xếp dọc theo một đường thẳng và được đánh số thứ tự lần lượt từ $1$ đến $n$, cổ vật thứ $i$ có giá trị $a_i$ ($i = 1, 2, \dots, n$). Thần đèn muốn Aladdin lấy đi các cổ vật tuỳ thích nhưng phải đảm bảo quy tắc của thế giới các vị thần. Theo đó, Aladdin phải lấy các cổ vật thoả mãn quy tắc sau:

• Cổ vật lấy sau phải có số thứ tự lớn hơn cổ vật lấy trước.
• Cổ vật lấy sau phải có giá trị lớn hơn cổ vật vừa lấy ngay trước đó và không được vượt quá giá trị k cho trước.

Aladdin rất thích các cổ vật và muốn lấy được các cổ vật theo đúng quy tắc của thần đèn đưa ra nhưng cũng phải có tổng giá trị lớn nhất mới hài lòng.

Yêu cầu: Hãy cho biết Aladdin có thể lấy được tổng giá trị các cổ vật lớn nhất là bao nhiêu?

Dữ liệu: Vào từ file RALADDIN.INP:

• Dòng đầu là 2 số nguyên dương $n$ và $k$ ($n \le 1000$; $0 < k \le 10^9$)
• Trong $n$ dòng sau, dòng thứ $i$ là số nguyên dương $a_i$ ($a_i \le 10^9$ với $i = 1, 2, \dots, n$).

Kết quả: Ghi vào file RALADDIN.OUT một số nguyên duy nhất là tổng giá trị các cổ vật lớn nhất mà Aladdin có thể lấy được.

• $n \le 1000$;
• $0 < k \le 10^9$;
• $a_i \le 10^9$.