Bài tập

Số tự nhiên chẵn là số tự nhiên chia hết cho 2.
Đếm xem có bao nhiêu số tự nhiên chẵn nằm trong đoạn \(a\) và \(b\).

Input

Dữ liệu vào: Đọc từ tệp DSC.INP ghi hai số tự nhiên \(a\) và \(b\) (\(0 \le a, b \le 10^{18}\)), hai số \(a\), \(b\) được ghi cách nhau bởi một dấu cách.

Output

Dữ liệu ra: Ghi vào tệp DSC.OUT chỉ ghi duy nhất một số là số lượng số tự nhiên chẵn tìm được

Example

0 8

5

Steph muốn cải thiện kiến thức về thuật toán của mình trong kỳ nghỉ đông. Cô ấy có tổng cộng \(X\) phút để dành cho việc học thuật toán. Có \(N\) thuật toán, và thuật toán thứ \(i\) cần \(a_i\) phút để học. Hãy tìm số lượng thuật toán lớn nhất mà Steph có thể học.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(X\) (\(1 \le N \le 100\), \(1 \le X \le 10^4\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 100\)).

\OutputFile

• In ra một số nguyên duy nhất là đáp án của bài toán.

\Examples
\beginexample
\exmp
6 15
4 3 8 4 7 3

4

\endexample

\Note
Trong ví dụ, Steph có thể học \(4\) thuật toán bằng cách chọn các thuật toán cần ít thời gian nhất, chẳng hạn các thời lượng \(3\), \(3\), \(4\), \(4\), có tổng thời gian là \(14\) phút.

\endproblem

Thám tử K cho phép chuỗi nhị phân có cặp \(00\) xuất hiện, nhưng chỉ không quá 2 lần. Hãy sử dụng đệ quy để liệt kê tất cả các chuỗi nhị phân có độ dài \(N\) thỏa mãn ràng buộc về số lần xuất hiện của cặp "00".

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 15\)).

Output

In ra số lượng chuỗi nhị phân thỏa mãn điều kiện.

Example

1

2

2

4

3

8

4

15

Xây dựng hàm giaithua(n) để tính giai thừa của một số nguyên không âm \(n\). Giá trị trả về là \(n!\). Áp dụng hàm đã xây dựng để tính và in ra \(n!\) với \(n\) được nhập từ bàn phím.

\(n! = 1 \times 2 \times 3 \times \dots \times n\).

Input

• Một số nguyên không âm \(n\) (\(0 \leq n \leq 15\)).

Output

Một dòng duy nhất chứa giá trị của \(n!\).

Example

3

3! = 6