Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên. Ví dụ ~1, 4, 9, \dots~ là các số chính phương.

Yêu cầu: Đếm các cặp nguyên dương ~(i, j)~ thỏa mãn điều kiện: ~1 \le i < j \le n~ ~i \times j~ là số chính phương

Input

• Dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^5~).

Output

• Ghi ra một số nguyên duy nhất là số cặp ~(i, j)~ tìm được.

Sample Input 1

4

Sample Output 1

6

Đoàn trường X tổ chức hội thao với nhiều nội dung thi đấu sôi động. Một trong những nội dung đặc biệt là đua xe đạp đôi, trong đó hai vận động viên cùng ngồi trên một chiếc xe đạp và phối hợp di chuyển theo lộ trình đã định. Ban tổ chức có danh sách ~n~ vận động viên, được đánh số từ ~1~ đến ~n~, với trọng lượng lần lượt là ~a_1, a_2, \dots, a_n~ kg. Mỗi chiếc xe đạp có trọng tải tối đa là ~p~ kg, nên cần chọn ra hai vận động viên có tổng trọng lượng không vượt quá ~p~ để tham gia.

Yêu cầu: Hãy giúp Ban tổ chức đếm số cách chọn hai vận động viên để làm mẫu.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~p~ (~2 \le n \le 2 \times 10^5, 1 \le p \le 10^9~) - số lượng vận động viên và trọng tải của xe đạp.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) - tương ứng là trọng lượng của ~n~ vận động viên.

Output

• Ghi ra một số nguyên là số cách chọn một cặp vận động viên để làm mẫu.

Sample Input 1

5 9
4 8 4 1 10

Sample Output 1

4

Trong một thành phố tương lai, các robot có khả năng tự học hỏi và phát triển kỹ năng ngôn ngữ để giao tiếp với con người. Một trong số đó là Robot Alpha, một robot tiên tiến nhưng gặp vấn đề trong việc nhận diện và sắp xếp thông tin văn bản. Để giúp Alpha cải thiện khả năng này, một bài kiểm tra đặc biệt đã được thiết kế. Robot Alpha sẽ được cung cấp một chuỗi dữ liệu hỗn loạn và cần phải tái tạo lại một chuỗi mục tiêu đã được mã hóa. Tuy nhiên, Alpha không thể tự do nhập ký tự mà phải tuân theo quy tắc di chuyển đặc biệt.

Cách Robot Alpha hoạt động:

• Di chuyển liền kề: Alpha có thể di chuyển đến ký tự kề bên trái hoặc kề bên phải trong chuỗi hiện tại và sao chép ký tự đó vào kết quả.
• Di chuyển bằng kết nối dữ liệu: Alpha có thể dịch chuyển đến bất kỳ vị trí nào trong chuỗi có cùng ký tự với vị trí hiện tại mà không cần sao chép ký tự vào kết quả. Điều này giúp Alpha di chuyển nhanh hơn mà không thay đổi nội dung của kết quả.

Việc di chuyển tốn ~|x - y|~ giây, trong đó ~x~ và ~y~ là vị trí của ký tự ban đầu và ký tự mới.

Yêu cầu: Alpha phải tạo ra chuỗi mã hóa mục tiêu trong thời gian ngắn nhất.

Input

• Dòng đầu tiên chứa một số nguyên ~n, m~ (~1 \le n, m \le 3000~).
• Dòng thứ hai chứa ~n~ kí tự in thường, là chuỗi dữ liệu hỗn loạn ban đầu.
• Dòng thứ ba chứa chuỗi mục tiêu được mã hóa.

Output

• Ghi ra thời gian ngắn nhất. Nếu không tạo được chuỗi mục tiêu thì in ra ~-1~.

Sample Input 1

2 2
Wa
ac

Sample Output 1

-1

Sample Input 2

10 5
Doofenferb
feren

Sample Output 2

7

Bạn là một phi hành gia đang thực hiện nhiệm vụ khám phá một hành tinh xa xôi. Con tàu của bạn đã hạ cánh xuống bề mặt hành tinh, và bạn cần thu thập các tinh thể năng lượng để duy trì hệ thống sự sống của mình.

Trên hành tinh này có ~n~ điểm thu thập tinh thể được đánh số từ ~1~ đến ~n~. Mỗi điểm thu thập chứa một tinh thể có giá trị năng lượng ~a_i~. Nếu ~a_i~ là số dương, bạn nhận thêm năng lượng. Nếu ~a_i~ là số âm, bạn sẽ bị tiêu hao năng lượng nếu thu thập tinh thể này. Bạn có thể chọn thu thập hoặc bỏ qua từng tinh thể, nhưng tổng năng lượng của bạn không bao giờ được phép âm. Mục tiêu của bạn là thu thập nhiều tinh thể nhất có thể khi di chuyển từ điểm đầu tiên đến điểm cuối cùng.

Yêu cầu: Tìm số lượng tinh thể tối đa có thể thu thập được.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 2 \times 10^5~) - số điểm thu thập tinh thể.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ (~-10^9 \le a_i \le 10^9~) - giá trị năng lượng của từng tinh thể.

Output

• Ghi ra một số nguyên duy nhất - số lượng tinh thể tối đa.

Sample Input 1

6
4 -4 1 -3 1 -3

Sample Output 1

5