자판기

어느 자판기가 $1$번부터 $n$번까지 번호가 매겨진 $n$가지 종류의 과자를 판매한다. $i$번 과자의 가격은 $c_i$이고, 자판기에는 현재 $i$번 과자가 $l_i$개 들어 있다.

이 자판기는 고장이 나 있다. $i$번 과자를 하나 구매하면(재고가 $1$개 이상 남아 있는 종류만 구매할 수 있다) 자판기는 $c_i$만큼의 돈을 받은 뒤, 그 과자와 함께 재고가 남아 있는 $1, 2, \ldots, i-1$번의 모든 종류에서 과자를 하나씩 더 내보낸다. $1$번부터 $i-1$번 중 이미 품절된 종류는 그냥 건너뛴다. 이렇게 나온 과자(직접 구매한 것과 덤으로 나온 것 모두)는 해당 종류의 남은 재고를 각각 $1$개씩 줄인다.

처음에 $k$만큼의 돈을 가지고 있고, 원하는 순서로 계속 과자를 구매할 수 있으며, 돈을 모두 쓸 필요는 없다. 지출이 $k$를 넘지 않도록 하면서 얻을 수 있는 과자들의 가격 합(직접 산 것과 덤 모두 포함)의 최댓값을 구하여라.

첫째 줄에 두 정수 $n$과 $k$가 주어진다 $(1 \le n \le 40,\ 1 \le k \le 64000)$. 각각 과자 종류의 수와 가지고 있는 돈의 양이다.

둘째 줄에 $n$개의 정수 $c_1, c_2, \ldots, c_n$이 주어진다 $(1 \le c_i \le 40)$. 각 종류의 가격이다.

셋째 줄에 $n$개의 정수 $l_1, l_2, \ldots, l_n$이 주어진다 $(0 \le l_i \le 40)$. 자판기에 들어 있는 각 종류의 개수이다.

$k$ 이하의 돈만 사용하여 얻을 수 있는 과자 가격 합의 최댓값을 정수 하나로 출력한다.

첫 번째 예제에서는 먼저 $6$번 과자를 산다(가격 $c_6 = 2$ 지불). 그러면 자판기가 $1, 2, 4, 5$번 과자도 하나씩 내보낸다($3$번은 품절이라 건너뛴다). 이어서 $4$번 과자를 산다(가격 $c_4 = 5$ 지불). 그러면 $2$번 과자가 하나 더 나온다. 두 번의 구매에 든 돈은 $2 + 5 = 7 \le 8$이고, 얻은 과자들의 가격 합은 $30$이다.