Oğurluq
Buxarestin mərkəzində çox böyük bir bank və onun içində çox böyük bir seyf var. Seyfdə N sayda böyük qutu yerləşir və bu qutular 1-dən N-ə qədər nömrələnib. k nömrəli qutunun içində k sayda böyük almaz var, hər bir almazın çəkisi W_k və dəyəri C_k-dir.
Hal-hazırda John və Brus seyfdədirlər. Onlar bütün almazları oğurlamaq istəyirlər, lakin təəssüf ki, daşıya biləcəkləri almazların ümumi çəkisi M-dən çox ola bilməz.
Sizin vəzifəniz John və Brus-a, ümumi çəkisi M-dən az və ya bərabər olan və mümkün olan ən yüksək ümumi dəyərə malik almazları seçməkdə kömək etməkdir.
Giriş verilənləri
Birinci sətir tək ədəd T – test hallarının sayını göstərir. Hər bir test halı iki ədəd N və M olan bir sətirlə başlayır, bu ədədlər bir boşluqla ayrılır. Növbəti sətir N ədəd W_k ehtiva edir və bu ədədlər bir boşluqla ayrılır. Sonrakı sətir N ədəd C_k ehtiva edir və bu ədədlər bir boşluqla ayrılır.
Çıxış verilənləri
Hər bir test halı üçün almazların mümkün olan ən yüksək ümumi dəyərini ehtiva edən bir sətir çap edin.
Məhdudiyyətlər
1 <= T <= 74,
1 <= N <= 15,
1 <= M <= 1000000000 (10^9),
1 <= W_k, C_k <= 1000000000 (10^9).