Sau vài lần được chim thần đưa đi lấy kho báu, Tèo em có cuộc sống sung túc và chuyển đi nơi khác. Lúc này Cuội được về ở đây để quản lý cây khế và ruộng vườn của người anh.

Chim thần lại đến vì lỡ yêu thích khế ở đây mất rồi. Như những lần trước, chim thần lại chở Cuội đi lấy châu báu. Lần này chim chở Cuội đến một đảo hoang để lấy vàng. Trên đảo này có một đường hầm dài một chiều, chỉ vừa đủ rộng để đi từ bên này sang bên kia một lần duy nhất. Trong đường hầm này có \(N\) đống vàng, đống thứ \(i\) có \(w_i\) (gr) vàng. Trên cửa hầm có ghi một lời nguyền không được lấy vàng ở hai đống liên tiếp, nếu không thì hầm sẽ sập xuống và chôn vùi tất cả mọi thứ. Cuội chỉ mang theo cái túi \(3\) gang chịu sức nặng tối đa là \(K\). Hỏi Cuội có thể lấy được tối đa bao nhiêu vàng?

Dữ liệu vào

• Dòng đầu tiên là số \(T\) - Là số trường hợp thử nghiệm
• \(T\) cặp dòng tiếp theo:
  • Dòng đầu chứa số nguyên \(N\) và \(K\).
  • Dòng hai chứa dãy \(w_1,w_2..w_N\) - Là lượng vàng ở \(N\) đống

Dữ liệu ra

• Ghi ra \(T\) số nguyên cách nhau dấu cách: Mỗi số nguyên lần lượt là đáp án cho một thử nghiệm.

Ràng buộc

• \(1 \le N, K, w_i \le 2024\)
• \(1 \le T \le 30\)

Input 1

2
5 100
50 10 20 30 40
5 87
21 45 30 12 14

Output 1

90 65

Input 2

3
5 120
50 10 20 30 40
7 82
18 28 19 28 12 25 13
7 123
23 26 19 28 21 22 32

Output 2

110 81 95