비스킷 담기 (biscuits)

$x$명이 참가하는 대회를 주관하고 있는 안티 콩은 각 참가자들에게 비스킷 가방을 하나씩 나눠 주려 한다. 서로 다른 $k$가지 종류의 비스킷에는 $0$부터 $k-1$까지 번호가 붙어 있다. $0 \leq i \leq k-1$인 $i$에 대해, $i$번 비스킷은 맛 점수가 $2^i$이고, 안티 콩은 창고에 $i$번 비스킷을 $a[i]$개 갖고 있다($a[i]$는 $0$일 수 있다).

안티 콩은 각 비스킷 가방에 모든 종류의 비스킷을 $0$개 이상씩 담으려고 한다. 모든 가방에 담긴 $i$번 비스킷의 개수의 합은 $a[i]$개를 넘을 수 없다. 한 가방에 담긴 모든 비스킷의 맛 점수의 합을 그 가방의 총 맛이라고 한다.

각 가방의 총 맛이 $y$가 되도록 $x$개의 비스킷 가방을 만들 수 있는 서로 다른 $y$ 값이 얼마나 많은지 안티 콩이 찾을 수 있도록 도와라.

구현 세부사항

다음 함수를 구현해야 한다.

int64 count_tastiness(int64 x, int64[] a)

• $x$: 싸야 할 비스킷 가방의 개수.
• $a$: 길이 $k$인 배열. $0 \leq i \leq k-1$인 $i$에 대해, $a[i]$는 창고에 있는 $i$번 비스킷의 개수를 나타낸다.
• 이 함수는 각 가방의 총 맛이 $y$가 되도록 안티 콩이 $x$개의 비스킷 가방을 쌀 수 있는 서로 다른 $y$ 값의 개수를 리턴해야 한다.
• 이 함수는 총 $q$번 호출된다($q$의 범위는 제약 조건과 서브태스크를 참고). 각각의 호출은 독립적이다.

예제

예제 1

다음 호출을 고려해 보자.

count_tastiness(3, [5, 2, 1])

안티 콩은 $3$개의 비스킷 가방을 싸려 하고, 창고에는 $3$종류의 비스킷이 있다.

• 맛 점수가 $1$인 $0$번 비스킷 $5$개,
• 맛 점수가 $2$인 $1$번 비스킷 $2$개,
• 맛 점수가 $4$인 $2$번 비스킷 $1$개.

가능한 $y$ 값들은 $[0,1,2,3,4]$이다. 예를 들어, 총 맛이 $3$인 비스킷 가방을 $3$개 싸려면 안티 콩은 다음과 같이 할 수 있다.

• $0$번 비스킷을 세 개 담은 가방 하나와
• $0$번 비스킷 한 개와 $1$번 비스킷 한 개를 담은 가방 둘.

가능한 $y$ 값이 $5$가지이므로, 함수는 $5$를 리턴해야 한다.

예제 2

다음 호출을 고려해 보자.

count_tastiness(2, [2, 1, 2])

안티 콩은 $2$개의 비스킷 가방을 싸려 하고, 창고에는 $3$종류의 비스킷이 있다.

• 맛 점수가 $1$인 $0$번 비스킷 $2$개,
• 맛 점수가 $2$인 $1$번 비스킷 $1$개,
• 맛 점수가 $4$인 $2$번 비스킷 $2$개.

가능한 $y$ 값들은 $[0,1,2,4,5,6]$이다. 가능한 $y$ 값이 $6$가지이므로, 함수는 $6$을 리턴해야 한다.

제약 조건

• $1 \leq k \leq 60$
• $1 \leq q \leq 1000$
• $1 \leq x \leq 10^{18}$
• 모든 $0 \leq i \leq k-1$에 대해 $0 \leq a[i] \leq 10^{18}$
• 각 count_tastiness 호출에 대해, 창고에 있는 모든 비스킷의 맛 점수의 합은 $10^{18}$을 넘지 않는다.

서브태스크

1. (9점) $q \leq 10$이고, 각 count_tastiness 호출에 대해 창고에 있는 모든 비스킷의 맛 점수의 합은 $100\;000$을 넘지 않는다.
2. (12점) $x=1$, $q \leq 10$
3. (21점) $x \leq 10\;000$, $q \leq 10$
4. (35점) 각 count_tastiness 호출의 올바른 리턴 값은 $200\;000$을 넘지 않는다.
5. (23점) 추가적인 제한은 없다.

샘플 그레이더는 첫 줄에서 정수 $q$를 읽는다. 그 뒤에 $q$쌍의 줄이 따라오며, 각 쌍은 하나의 시나리오를 다음 형식으로 나타낸다.

• $1$번째 줄: $k\;x$
• $2$번째 줄: $a[0]\;a[1]\;\ldots\;a[k-1]$

• $i$번째 줄 ($1 \leq i \leq q$): 입력의 $i$번째 시나리오에 대한 count_tastiness의 리턴 값