Cho một số tự nhiên ~N~ ~(N \le 10^{64})~.

Yêu cầu

Hãy viết chương trình tính tổng bình phương các chữ số của số tự nhiên đã cho.

Ví dụ: ~N = 1234~. Tổng bình phương các chữ số của nó là: ~1^2 + 2^2 + 3^2 + 4^2 = 30~.

Dữ liệu đầu vào

Gồm một số tự nhiên ~N~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng bình phương các chữ số của ~N~.

Ràng buộc dữ liệu

• Có 60% test tương ứng 60% số điểm của bài với ~N \le 10^6~;
• Có 20% test tương ứng 20% số điểm của bài với ~N \le 10^{18}~;
• Có 20% test khác tương ứng với 20% số điểm còn lại của bài với ~N \le 10^{64}~.

Ví dụ

Ví dụ 1

INPUT

1234

OUTPUT

30

Để chuẩn bị cho Kỳ thi học sinh giỏi môn Tin học cấp tỉnh năm học 2024 - 2025. Ban tổ chức cần chuẩn bị phòng máy cho phần thi lập trình. Phòng máy có ~m~ máy tính, công việc của ban tổ chức là sử dụng ổ điện có dây để cung cấp điện cho ~m~ máy tính. Phòng máy chỉ có một ổ điện có một khe cắm ở trên tường là đang có điện và được gọi là ổ điện nguồn. Hiện tại trong nhà kho có ~n~ ổ cắm điện có dây, mỗi ổ điện có một số khe cắm và một đường dây nối có phích cắm để có thể cắm đến ổ điện khác. Ta gọi các ổ điện này là ổ điện rời. Một ổ điện rời có điện khi mà phích cắm của nó được cắm vào ổ điện nguồn hoặc cắm vào khe của một ổ điện rời đang có điện. Chú ý là chỉ có một ổ điện rời được cắm vào ổ điện nguồn và mỗi khe chỉ có duy nhất một phích cắm được cắm vào.

(Ổ cắm điện rời có 6 khe cắm)

Để cung cấp điện cho ~m~ máy tính, mỗi máy tính cần được cắm vào một khe của ổ điện rời đang có điện. Cho biết số khe cắm của ổ điện rời thứ ~i~ là ~a_i~ ~(1 \le a_i \le 10;\ i = 1, 2, 3, ..., n)~. Ban tổ chức muốn sử dụng số ổ điện rời với số lượng ít nhất nhưng vẫn có thể cung cấp nguồn điện cho ~m~ máy tính.

Yêu cầu

Tính xem số lượng ổ điện rời ít nhất cần sử dụng là bao nhiêu.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~ tương ứng là số ổ điện rời và số máy tính.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10)~ lần lượt là số khe cắm của ~n~ ổ điện.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng ổ rời ít nhất cần sử dụng để cung cấp điện cho ~m~ máy tính. Nếu sử dụng cả ~n~ ổ điện rời mà không cung cấp điện cho ~m~ máy tính thì đưa ra ~-1~.

Ràng buộc dữ liệu

• Có 50% số test ~1 \le n, m \le 100;\ a_1 = a_2 = ... = a_n = 2~;
• Có 50% số test còn lại ~100 < n, m \le 1000~.

Ví dụ

Ví dụ 1

INPUT

3 4
3 2 2

OUTPUT

2

Ví dụ 2

INPUT

5 5
1 3 1 2 1

OUTPUT

-1

Có ~n + 1~ cây cột, đánh số bắt đầu từ ~1~ đến ~n + 1~ tính từ trái qua phải. Cây cột thứ ~i~ có độ cao ~h_i~ ~(i = 1..n,\ 0 < h_i \le 10^9,\ 0 < n \le 10^6,\ h_i \in \mathbb{Z})~, cây cột ~n + 1~ có độ cao lớn hơn mọi cây cột trước đó, ta ký hiệu độ cao này là ~-1~ (vì không cần biết chính xác).

Trên mỗi cây cột hiện có một con cào cào đang sống. Đến tuổi trưởng thành, mỗi con cào cào đều muốn đi tìm một chỗ sống tốt đẹp hơn bằng cách nhảy sang cây cột cao hơn gần nhất bên phải. Cào cào ở cây cột thứ ~i~ có thể thực hiện được ~x_i~ bước nhảy ~(0 < x_i < n)~.

Ví dụ: Có ~8~ cây cột với độ cao tương ứng từ trái sang phải là ~3, 1, 4, 5, 6, 2, 3~ và ~8~. Số bước nhảy mỗi cào cào có thể thực hiện là ~1, 2, 1, 3, 4, 2, 1, 2~. Sau khi di chuyển hết khả năng của mình, cào cào ở cây cột ~1~ sẽ tới được cây cột ~3~ với độ cao là ~4~, còn cào cào ở cây cột ~4~ tới được cây cột ~n + 1~ (độ cao ~-1~).

Yêu cầu

Hãy xác định độ cao nơi ở mới của mỗi con cào cào.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~h_1, h_2, ..., h_n~.
• Dòng thứ ba chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~.

Dữ liệu đầu ra

Gồm một dòng chứa ~n~ số nguyên là độ cao nơi ở mới của mỗi con cào cào.

Ràng buộc dữ liệu

• Có 50% số test ~n \le 10^4~;
• Có 50% số test còn lại ~n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

4 5 5 -1 -1 8 8 -1

Có ~n~ học sinh được xếp thành một hàng. Học sinh thứ ~i~ được cấp một bảng nhỏ, trên đó viết một số nguyên ~a_i~ ~(|a_i| \le 10^9)~.

Một phép chia dãy học sinh ban đầu thành ~k~ đoạn liên tiếp được biểu diễn bằng dãy số nguyên:

~0 = x_{0} < x_{1} < x_{2} < ... < x_{k-1} < x_k = n~

Trong đó đoạn thứ ~j~ gồm các học sinh vị trí từ ~x_{j - 1} + 1~ đến ~x_j~.

Yêu cầu

Cho số nguyên ~m~, hãy tìm cách chia học sinh thành một số ít nhất các đoạn liên tiếp sao cho tổng các số trong mỗi đoạn không vượt quá ~m~.

Ví dụ: với ~n = 11,\ m = 5~; dãy học sinh cầm bảng ~= (9, -1, 2, -6, 1, 2, 3, -4, 3, 9, -4)~, thì có thể chia thành ~3~ đoạn con liên tiếp:

~a_{1...5} = (9, -1, 2, -6, 1);\ a_{6...9} = (2, 3, -4, 3);\ a_{10...11} = (9, -4)~

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa hai số nguyên dương ~n, m~ ~(n \le 10^5,\ m \le 10^9)~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^9,\ \forall i \in [1, n])~.

Dữ liệu vào đảm bảo luôn tồn tại cách chia dãy.

Dữ liệu đầu ra

Gồm hai dòng:

• Dòng thứ nhất ghi số đoạn để chia dãy;
• Dòng thứ hai ghi ~k - 1~ số nguyên ~x_1, x_2, ..., x_{k-1}~ của phép chia tương ứng.

Ràng buộc dữ liệu

• Có 50% số test ~n \le 5555~;
• Có 50% số test còn lại ~n \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

11 5
9 -1 2 -6 1 2 3 -4 3 9 -4

OUTPUT

3
5 9