Problem Statement

Given a positive integer N, find the maximum integer k such that 2^k \le N.

Constraints

• N is an integer satisfying 1 \le N \le 10^{18}.

Sample Input 1

6

Sample Output 1

2

• k=2 satisfies 2^2=4 \le 6.
• For every integer k such that k \ge 3, 2^k > 6 holds.

Therefore, the answer is k=2.

Sample Input 2

1

Sample Output 2

0

Note that 2^0=1.

Sample Input 3

1000000000000000000

Sample Output 3

59

The input value may not fit into a 32-bit integer.

Problem Statement

You are given an N \times N grid S and an M \times M grid T. The cell at the i-th row from the top and the j-th column from the left is denoted by (i,j).

The colors of the cells in S and T are represented by N^2 characters S_{i,j} (1\leq i,j\leq N) and M^2 characters T_{i,j} (1\leq i,j\leq M), respectively. In grid S, cell (i,j) is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies for grid T.

Find T within S. More precisely, output integers a and b (1 \leq a,b \leq N-M+1) that satisfy the following condition:

• S_{a+i-1,b+j-1} = T_{i,j} for every i,j (1\leq i,j \leq M).

Constraints

• 1 \leq M \leq N \leq 50
• N and M are integers.
• Each of S_{i,j} and T_{i,j} is . or #.
• There is exactly one pair (a,b) satisfying the condition.

Sample Input 1

3 2
#.#
..#
##.
.#
#.

Sample Output 1

2 2

The 2 \times 2 subgrid of S from the 2nd to the 3rd row and from the 2nd to the 3rd column matches T.

Sample Input 2

2 1
#.
##
.

Sample Output 2

1 2

Problem Statement

There are M sets, called S_1, S_2, \dots, S_M, consisting of integers between 1 and N.
S_i consists of C_i integers a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}.

There are (2^M-1) ways to choose one or more sets from the M sets.
How many of them satisfy the following condition?

• For all integers x such that 1 \leq x \leq N, there is at least one chosen set containing x.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 10
• 1 \leq C_i \leq N
• 1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
• All values in the input are integers.

Sample Input 1

3 3
2
1 2
2
1 3
1
2

Sample Output 1

3

The sets given in the input are S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace.
The following three ways satisfy the conditions in the Problem Statement:

• choosing S_1, S_2;
• choosing S_1, S_2, S_3;
• choosing S_2, S_3.

Sample Input 2

4 2
2
1 2
2
1 3

Sample Output 2

0

There may be no way to choose sets that satisfies the conditions in the Problem Statement.

Sample Input 3

6 6
3
2 3 6
3
2 4 6
2
3 6
3
1 5 6
3
1 3 6
2
1 4

Sample Output 3

18

Problem Statement

There are N dishes, and the i-th dish has a sweetness of A_i and a saltiness of B_i.

Takahashi plans to arrange these N dishes in any order he likes and eat them in that order.

He will eat the dishes in the arranged order, but he will stop eating as soon as the total sweetness of the dishes he has eaten exceeds X or the total saltiness exceeds Y.

Find the minimum possible number of dishes that he will end up eating.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X, Y \leq 2 \times 10^{14}
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

4 7 18
2 3 5 1
8 8 1 4

Sample Output 1

2

The i-th dish will be denoted as dish i.

If he arranges the four dishes in the order 2, 3, 1, 4, as soon as he eats dishes 2 and 3, their total sweetness is 8, which is greater than 7. Therefore, in this case, he will end up eating two dishes.

The number of dishes he will eat cannot be 1 or less, so print 2.

Sample Input 2

5 200000000000000 200000000000000
1 1 1 1 1
2 2 2 2 2

Sample Output 2

5

Sample Input 3

8 30 30
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1

Sample Output 3

6

Problem Statement

Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.

Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.

Constraints

• 1\leq N\leq 50
• 1\leq X\leq 10^4
• 1\leq A_i\leq 100
• 1\leq B_i\leq 50
• A_i are pairwise distinct.
• All values in the input are integers.

Sample Input 1

2 19
2 3
5 6

Sample Output 1

Yes

Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen. Thus, Yes should be printed.

Sample Input 2

2 18
2 3
5 6

Sample Output 2

No

There is no combination of the coins that he can use to pay exactly 18 yen. Thus, No should be printed.

Sample Input 3

3 1001
1 1
2 1
100 10

Sample Output 3

Yes

He need not use all kinds of coins.