minict04

corona

Cho số nguyên n, hãy phân tích n thành tổng của k số nguyên tố sao cho k lớn nhất có thể.

Input

  • Dòng đầu tiên là số nguyên n (~2 <= n <= 10^5~).

Output

  • Dòng đầu in ra một số nguyên là k.
  • Dòng thứ hai in ra k số nguyên có tổng bằng n theo thứ tự tăng dần.

Input

5

Output

2
2 3

Chụp ảnh

CaiWinDao

Buổi liên khối chuyên Tin của trường Nguyễn Bỉnh Khiêm diễn ra với sự tham gia của ~N~ học sinh. Cuối giờ, Oanh Trúc Béo ra hiệu cho các học sinh này xếp thành một hàng và đánh số họ từ ~1~ đến ~N~ tương ứng với vị trí đứng của họ trong hàng. Oanh Trúc muốn chụp một số tấm ảnh kỷ niệm cho buổi liên khối, mỗi tấm sẽ chụp lại một đoạn liên tiếp các bạn trong hàng. Vì là một sự kiện trong đại nên Trúc muốn mỗi bạn học sinh tham dự đều có mặt trong ít nhất một tấm ảnh.

Tuy nhiên, trong ~N~ học sinh này có tồn tại ~K~ đôi bạn xung khắc nhau (đã từng là bạn thân nhưng hiện tại tình nghĩa đã vô cùng rạn nứt vì crush chung một em gái nào đó), các đôi bạn xung khắc này đều không muốn đứng chung với nhau trong một tấm ảnh. Bộ nhớ của điện thoại Oanh Trúc không còn nhiều nên cô ấy đã nhờ bạn lập trình tính toán số tấm ảnh ít nhất cần chụp để thỏa mãn tất cả các ràng buộc trên.


Input

Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ (~2\leq N\leq 10^9~, ~2\leq K\leq 1000~).

Dòng thứ ~i~ trong ~K~ dòng tiếp theo chứa hai số nguyên dương phân biệt ~A_i~ và ~B_i~ thể hiện một đôi bạn xung khắc ~\left(A_i, B_i\right)~ - họ không thể cùng đứng chung trong một tấm ảnh.


Output

Một số nguyên duy nhất là số tấm ảnh ít nhất mà Oanh Trúc Béo cần chụp.


Ví dụ

Sample input
7 3
1 3
2 4
5 6
Sample output
3
Giải thích

Trúc có thể chụp ~3~ tấm ảnh như sau:

  • Tấm đầu tiên chụp học sinh ~1~ và học sinh ~2~.
  • Tấm thứ hai chụp từ học sinh ~3~ đến học sinh ~5~.
  • Tấm cuối cùng chụp học sinh ~6~ và học sinh ~7~.

Tam giác không cân

PhanDinhKhoi, daicadihoc

Để tham gia câu lạc bộ Origami của trường, Huy phải:

"Viết chương trình kiểm tra xem 3 số nguyên dương nhập vào có thể là 3 cạnh của một tam giác KHÔNG cân hay không."

Vì laptop của Huy đã bị hỏng, bạn hãy giúp Huy giải bài tập trên. Biết rằng tam giác đều là tam giác cân.

Dữ liệu vào

  • Một dòng duy nhất gồm 3 số nguyên dương ~ a,b,c \left(a,b,c\leq 10^{18}\right)~

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Kết quả

  • Ghi ra "YES" nếu 3 số nguyên dương là 3 cạnh của của một tam giác KHÔNG cân, ngược lại in ra "NO"

Sample Input

3 4 5

Sample Output

YES

Nguồn: Codeforces

Nén xâu

admin, daicadihoc

Một xâu ký tự có thể nén lại thành một xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau. Ví dụ trong xâu aaaa sẽ nén thành 4a. Hãy lập trình để nén một xâu ký tự thường theo cách trên.

Input:

  • Một xâu các ký tự là chữ cái thường có tối đa ~10^5~ ký tự.

Output:

  • Một xâu ký tự sau khi nén.

Ví dụ

Input

mmaabbbeeeezh

Output

2m2a3b4ezh

Xếp hàng

Small

Hàng ngày khi lấy sữa, ~N~ con bò của bác John (~1 ≤ N ≤ 50000~) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá chênh lệch về chiều cao.

Bác John đã chuẩn bị một danh sách gồm ~Q\ (1 ≤ Q ≤ 200000)~ đoạn các con bò và chiều cao của chúng (trong phạm vi ~[1, 1000000]~). Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữa con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này!

Dữ liệu
  • Dòng đầu tiên chứa 2 số nguyên ~N~ và ~Q~.
  • Dòng thứ ~i~ trong số ~N~ dòng sau chứa 1 số nguyên duy nhất, là độ cao của con bò thứ ~i~.
  • Dòng thứ ~i~ trong số ~Q~ trong tiếp theo chứa 2 số nguyên ~A, B (1 ≤ A ≤ B ≤ N)~, cho biết đoạn các con bò từ ~A~ đến ~B~.
Kết quả
  • Gồm ~Q~ dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao giữa con bò thấp nhất và cao nhất thuộc đoạn tương ứng.
Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Output
6
3
0

Nguồn: vn.spoj.vn

Cặp số đặc biệt

AhhShibaaa

Hôm nay Nhật học toán trên lớp về chủ đề số đặc biệt. Thầy giáo định nghĩa một số nguyên dương ~x~ bất kì là số đặc biệt nếu như các chữ số của ~x~ đều giống nhau. Ví dụ: ~22, 3333, 1~ là số đặc biệt, còn ~123, 96, 1801~ không phải là số đặc biệt.

Cho dãy số ~A~ gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. Hãy đếm số cặp chỉ số ~(i, j)~ sao cho:

  • ~1 ≤ i < j ≤ n~
  • ~a_i + a_j~ là một số đặc biệt

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương ~n~ ~(1 ≤ n ≤ 2 * 10^5)~
  • Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ ~(1 ≤ a_i ≤ 10^6)~

Dữ liệu ra:

  • In ra số cặp chỉ số cần tìm.

Sample Input

5
1 2 3 4 5

Sample Output

10

Tặng quà

admin

Nhân dịp nghỉ lễ, An được bố mẹ đưa lên nhà chị họ ở thành phố chơi, Bình chị họ của An rất vui mừng khi gặp cô em họ đã lâu không gặp. Hai chị em chơi đùa rất vui và không muốn chia tay nên Bình muốn tặng An một số món quà làm kỉ niệm. Bình có ~n~ món đồ chơi, và đặt chúng từ 1 đến ~n~, đồ chơi thứ ~i~ có giá trị là ~a_i~. Trong lúc chọn quà, Bình yêu cầu An không được chọn ~k~ món đồ chơi liên tiếp.

Yêu cầu: Hãy giúp An chọn các đồ chơi với tổng giá trị lớn nhất.

Dữ liệu vào

  • Dòng 1 : gồm 2 số ~n~ và ~k~ cách nhau bởi khoảng trắng.
  • Dòng 2 : : chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0≤ a_i ≤ 10^6~).

Kết quả

  • Ghi một số nguyên duy nhất là tổng giá trị các món đồ chơi lớn nhất mà An có thể chọn được.

Sample Input

5 3
6 19 8 7 13

Sample Output

45

Ràng buộc:

  • Có 50% số test ứng với 50% điểm của bài với ~n ≤ 10^3~.
  • Có 50% số test ứng với 50% điểm của bài với ~n ≤ 10^6~.

Nguồn: 2019 CLK

CSES - Increasing Array | Dãy tăng

Flower_On_Stone, SPyofgame, Namlenam

You are given an array of ~n~ integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input

  • The first input line contains an integer ~n~: the size of the array.
  • Then, the second line contains ~n~ integers ~x_1, x_2, ..., x_n~: the contents of the array.

Output

  • Print the minimum number of moves.

Constraints

  • ~1 \le n \le 2 \cdot 10^5~
  • ~1 \le x_i \le 10^9~

Example

Sample input

5
3 2 5 1 7

Sample output

5

Nhà nghiên cứu

admin

Tiền sĩ Hùng là một nhà nghiên cứu về các con số. Đề tài lần này ông được giao nhiệm vụ tìm ra một bài toán để kiểm tra năng lực của các học viên trong phòng thí nghiệm của ông. Nhưng tất cả các học viên của ông đều rất thông minh nên để thử tài họ phải là một bài toán cực khó. Con trai của ông năm nay vào lớp 3. Do ảnh hưởng của bố nên cậu ta cũng rất hứng thú với những con số. Trong khi Hùng đang nát óc nghĩ bài toán thì con trai của ông chỉ vào đống tài liệu về các dãy bit gồm toàn số 0, 1 và khoái chí nói rằng: “Ba ơi, đoạn bit này có 5 số 0 và 5 số 1 ba ạ. Con rất thích những thứ cân bằng như thế !!”. Cậu con trai vừa dứt lời, Hùng liền nghĩ ngay ra bài toán để thách đố học viên của mình. Quả nhiên sau đó tât cả đều chịu thua trước bài toán hóc búa này. Các bạn hãy giúp các bạn học viên giải quyết bài toán của Tiến sĩ Hùng nhé!!!! Bài toán như sau: “Cho dãy số A gồm N phần tử 0 hoặc 1. Tìm đoạn con liên tiếp dài nhất mà trong đó có số lượng số 0 và số lượng số 1 là như nhau”.

Dữ liệu vào:

  • Dòng thứ nhất gồm một số nguyên dương ~N~ ~\left(N \leq 10^5\right)~
  • Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, …, a_n~ (~a_i = {0,1}~) là dãy số cho trước.

Kết quả:

  • Một dòng ghi một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5
1 1 0 0 1

Sample Output

4

Sample Input

10
1 0 0 1 1 1 0 1 1 0

Sample Output

6

Sample Input

4
1 1 1 1

Sample Output

0

Giới hạn

  • Sub 1: 60% số điểm có ~N \leq 10^3~.
  • Sub 2: 40% số điểm có ~N \leq 10^5~.

Nguồn: 2019 HV-PT

Xếp gạch

Small

Cho ~N~ viên gạch hình chữ nhật có kích thước là ~a_i, b_i, h_i~ lần lượt là chiều dài, chiều rộng, chiều cao của viên gạch thứ ~i~.

Tìm cách xếp các khối gạch thành 1 tháp. Sao cho các cạnh của các viên gạch song song với nhau và hình chữ nhật ở phía trên nằm trọn trong hình chữ nhật phía dưới.

Viên gạch thứ ~j~ có thể nằm trên viên gạch thứ ~i~ khi ~a_i>a_j~ và ~b_i>b_j~

Tìm số viên gạch tối đa có thể chồng lên nhau và chiều cao tối đa của tháp.

Input

  • Dòng đầu tiên chứa một số nguyên dương ~N~ (~n\le 5000~) là số viên gạch
  • ~N~ dòng tiếp theo mỗi dòng chứa 3 số ~a_i, b_i, h_i~.

Output

  • Gồm 2 số ~x,y~ lần lượt là số viên gạch tối đa trong 1 tháp và chiều cao tối đa của tháp dựng tự các viên gạch

Input

10
9 7 1
10 4 8
8 5 5
7 4 10
7 4 8
5 1 9
2 1 10
3 2 4
5 4 5
10 3 2

Output

5 30

Nguồn: Thánh Ngốc

Kho lương (HSG10v2-2022)

Small

Bài 2: Kho lương (7 điểm)


Số cân bằng (THTA Sơn Trà 2022)

Small

Số cân bằng là số:

  • Có số lượng các chữ số là số chẵn
  • Nữa nhóm ký tự bên trái giống nữa nhóm bên phải

Ví dụ: ~66, 1212; 348348~ là số cân bằng, ~666, 1221; 334488~ không phải là số cân bằng

Yêu cầu Cho giá trị ~n~, hãy tìm các số cân bằng không vượt quá ~n~

Input

  • Một dòng chứa một số nguyên ~n\ (0< n \le 10^{12})~

Output:

  • In ra số lượng số cân bằng không vượt quá ~n~.

Input

33

Output

3

Input

1333

Output

13

Thi thử vòng 2 2022 - Bầu cử

skyvn97

Tại nước Cộng hòa VOI, có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Các thành phố được kết nối với ~N - 1~ đường hai chiều. Người dân ở Cộng hòa VOI đang đi lại giữa các thành phố bằng những con đường này. Họ có thể đi lại giữa hai thành phố bất kỳ bằng cách đi qua một hoặc một số con đường.

Ông PVH là ứng cử viên tổng thống của Cộng hòa VOI. Tất nhiên, để trở thành tổng thống, ông ta phải thực hiện chiến dịch tranh cử tổng thống. Thư ký của ông đã lên kế hoạch cho ~M~ chiến dịch tranh cử. Trong kế hoạch thứ ~i~, ông PVH sẽ đi từ thành phố ~A_i~ đến thành phố ~B_i~, sử dụng số con đường tối thiểu và phát biểu trước công chúng tại mỗi thành phố trên đường đi (bao gồm thành phố ~A_i~ và thành phố ~B_i~). Bởi vì thư ký của ông ấy rất giỏi, nên anh ta biết rằng ông PVH sẽ nhận được phiếu ~C_i~ nếu kế hoạch thứ ~i~ được thực hiện. Có thể thực hiện nhiều kế hoạch.

Tuy nhiên, những người ở Cộng hòa VOI rất thiếu kiên nhẫn. Nếu ông PVH phát biểu trước công chúng nhiều lần trong cùng một thành phố, ông sẽ mất sự ủng hộ từ người dân trong Cộng hòa VOI.

Bởi vì ông PVH muốn trở thành tổng thống, ông ấy muốn nhận được càng nhiều phiếu bầu càng tốt. Vì bạn là siêu lập trình viên ở Cộng hòa VOI, ông ấy đã yêu cầu bạn viết một chương trình tính toán số phiếu bầu tối đa mà ông PVH có thể nhận được trong cuộc bầu cử tổng thống với giả định rằng ông ấy sẽ không phát biểu trước công chúng nhiều lần trong cùng một thành phố.

Với ~N~ là số thành phố ở Cộng hòa VOI, thông tin về các con đường, ~M~ là số kế hoạch cho chiến dịch bầu cử và thông tin của từng kế hoạch, hãy viết một chương trình tính toán số phiếu bầu tối đa mà ông PVH có thể nhận được cuộc bầu cử tổng thống.

Input

Dòng đầu tiên chứa số nguyên ~N~ ~(2 \leq n \leq 10^5)~ là số thành phố tại nước cộng hoà VOI

~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1 \leq u, v \leq N, u \neq v)~ thể hiện con đường nối giữa thành phố ~u~ và thành phố ~v~.

Dòng tiếp theo chứa số nguyên ~M~ ~(1 \leq M \leq 10^5)~ là số kế hoạch tranh cử

~M~ dòng tiêp theo, dòng thứ ~i~ chứa ba số nguyên ~A_i, B_i, C_i~ ~(1 \leq A_i, B_i \leq N, A_i \neq B_i, 1 \leq C_i \leq 10^4)~ thể hiện kế hoạch thứ ~i~

Output

Gồm một dòng duy nhất là số phiếu tối đa ông PVH có thể nhận được

Subtask

Bộ test của bài được chia làm các subtask như sau:

  • Subtask 1 (10 điểm): ~M \leq 15~
  • Subtask 2 (5 điểm): ~X_i = i,Y_i = i + 1, C_i = 1~
  • Subtask 3 (5 điểm): ~X_i = i,Y_i = i + 1~
  • Subtask 4 (30 điểm): ~C_i = 1~
  • Subtask 5 (10 điểm): ~N \leq 1000, M \leq 1000~
  • Subtask 6 (40 điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~100~ điểm.

Ví dụ

Input

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

Output

8

Giải thích

Trong ví dụ ở trên, ông PVH thực hiện kế hoạch ~1~ và ~2~, do vậy số phiếu bầu nhận được là ~3 + 5 = 8~, đây là đáp án tối ưu.

CaiWinDao và em gái thứ 4

ami

Hôm nay CaiWinDao tổ chức sinh nhật cho em gái thứ 4 ở nhà mình. Sau khi tiệc tùng no nê, mọi người đã ra về, trong nhà chỉ còn hai anh em ở lại dọn dẹp. Thấy trời đã tối, đường về nhà em gái lại hiểm trở, CaiWinDao bèn ngỏ ý mời em gái ngủ lại nhà mình đêm nay.

Sau khi xem phim ma xong, CaiWinDao đưa em gái lên phòng ngủ. Sợ em khó ngủ, anh bày ra một trò chơi để em có thể chơi một mình trong đêm. CaiWinDao lấy ra ~n~ đồng xu, sắp thành 1 hàng liên tiếp. Ban đầu tất cả đồng xu đều nằm ngửa. Mỗi lượt chơi, em gái có thể lật ~k~ đồng xu liên tiếp (úp thành ngửa và ngược lại). CaiWinDao đố em gái có thể lật úp tất cả đồng xu.

Em gái rất hoang mang, không biết CaiWinDao có ý đồ xấu gì không? Các bạn hãy giúp em gái xem thử với ~n, k~ cho trước, em gái có thể chiến thắng trò chơi và đi ngủ không nhé!

Dữ liệu vào

Gồm 2 số nguyên ~n, k (1 \le k \le n \le 100)~.

Dữ liệu ra

In ra YES nếu em gái có thể chiến thắng, NO nếu em gái không thể thắng (và thức trắng đêm).

Ví dụ

input

4 2

output

YES

input

26 12

output

NO

input

20 4

output

YES

input

14 12

output

NO

Trong ví dụ 1, lượt đầu em gái có thể lật úp hai đồng 1, 2. Lượt 2 lật úp 2 đồng 3, 4.

Giả giai thừa

Small

Giai thừa của một số tự nhiên là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng nó. Ví dụ, giai thừa của 4 là ~1 × 2 × 3 × 4 = 24~. Giả giai thừa của ~n~ giống với giai thừa của ~n~, nhưng có một điểm khác là có đúng một thừa số bị thay thế bởi một số nguyên dương nhỏ hơn nó. Ví dụ: !1 × 2 × 2 × 4 = 16~ là một giả giai thừa của 4.

Yêu cầu: Cho số tự nhiên ~n~, một môđun nguyên tố ~p~ và một số dư ~r~, hãy tìm giả giai thừa của ~n~ sao cho nó có số dư ~r~ khi chia cho ~p~.

Dữ liệu

  • Một dòng chứa 3 số nguyên ~n, p~ và ~r~ (~2 ≤ n ≤ 10^{18}, 2 ≤ p < 10^7, 0 ≤ r < p~) như mô tả ở trên.

Kết quả

  • Nếu không có giả giai thừa nào thỏa mãn thì ghi ra “-1 -1”. Ngược lại ghi ra hai số nguyên tương ứng là thừa số ~k~ (~2 ≤ k ≤ n~) và giá trị ~v~ của số thay thế thừa số (~1 ≤ v < k~). Nếu có nhiều cặp (~k, v~) thỏa mãn thì đưa ra cặp (~k, v~) nhỏ nhất theo thứ tự từ điển.

Sample input

4 5 1

Sample output

3 2

Sample input

4 127 24

Sample output

-1 -1

Giải thích: Với ví dụ đầu tiên, dữ liệu ra mô tả giả giai thừa là ~1 × 2 × 2 × 4 = 16 ≡ 1 (\mod 5)~.

Ràng buộc

  • Subtask 1 (41%): ~n ≤ 14.~
  • Subtask 2 (21%): ~r = 0.~
  • Subtask 3 (38%): Như ràng buộc gốc.

Nguồn: Central Europe Regional Contest 2017

Hoa thành thường

admin

Cho một chuỗi kí tự gồm ~n~ kí tự bất kì (~n \leq 100~). Hãy đổi tất cả chữ hoa có trong chuỗi thành chữ thường. Xuất chuỗi ra màn hình.

Input:

  • Gồm một dòng duy nhất là một chuỗi kí tự

Output:

  • In chuỗi đã đổi ra màn hình

Ví dụ

Input:

4I1K2D14Ti

Output:

4i1k2d14ti

Tháp lũy thừa (THT TQ 2013)

letangphuquy

Bài 2 THT bảng B, năm 2013

Tháp lũy thừa (power tower) hay lũy thừa lặp (iterated power) là một phép toán thường được sử dụng để biểu diễn những giá trị rất lớn. Với hai số nguyên ~a~ và ~n~ ~(a > 0, n \ge 0)~, tháp lũy thừa bậc ~n~ của ~a~ (kí hiệu ~a \uparrow \uparrow n~) định nghĩa như sau:

  • ~a \uparrow \uparrow n = 1~, nếu ~n = 0~
  • ~a \uparrow \uparrow n = a^{a \uparrow\uparrow n - 1} = a^{a^{...^{a}}} ~ (~n~ cấp), nếu ~n > 0~

Ví dụ:

~2 \uparrow\uparrow 1 = 2~

~2 \uparrow\uparrow 2 = 2^2 = 4~

~2 \uparrow\uparrow 3 = 2^{2^2} = 2^4 = 16~

~2 \uparrow\uparrow 4 = 2^{2^{2^2}} = 2^{16} = 65536~

~3 \uparrow\uparrow 3 = 3^{3^3} = 3^{27} = 7625597484987~

Yêu cầu: cho ba số nguyên dương ~a, n, m~, hãy cho biết số dư trong phép chia ~(a \uparrow\uparrow n)~ cho ~m~.

Input

3 số nguyên dương ~a, n, m (a, n, m \le 10^6)~

Output

Kết quả bài toán

Example

Sample Input 1:

2 4 100

Sample Output 1:

36

Sample Input 2:

11 2 100

Sample Output 2:

11

Vòng sơ loại OLP Miền Trung Tây Nguyên - Phòng thủ

Flower_On_Stone

Hôm nay bạn sẽ dẫn đầu một nhóm cung thủ yêu tinh để bảo vệ lâu đài bị tấn công bởi một đội quân Orc giận dữ. Ba mặt của lâu đài được bảo vệ bởi những ngọn núi không thể vượt qua và mặt còn lại được bao phủ bởi một bức tường dài được chia thành ~n~ phần. Tại thời điểm này, có chính xác ~a_i~ cung thủ đứng ở phần thứ ~i~ của bức tường này. Bạn biết rằng cung thủ đứng ở phần i có thể bắn những con Orc tấn công phần nằm ở khoảng cách không quá ~r~ , đó là tất cả những phần ~j~ sao cho ~|i-j| \le r~. Đặc biệt, ~r = 0~ có nghĩa là cung thủ chỉ có thể bắn vào lũ Orc tấn công phần ~i~.

Biểu thị của cấp độ phòng thủ của phần ~i~ là tổng số cung thủ có thể bắn vào lũ Orc tấn công phần này. Độ tin cậy của kế hoạch phòng thủ là giá trị tối thiểu của mức độ phòng thủ của phần tường riêng lẻ.

Chỉ còn một ít thời gian nữa là đến cuộc tấn công nên bạn không thể phân bổ lại các cung thủ đã ở trên tường. Tuy nhiên, có một lượng dự trữ ~k~ cung thủ mà bạn có thể phân phối giữa các phần tường theo cách tùy ý, tuy nhiên với phần thứ ~i~ có sức chứa tối đa là ~b_i~ cung thủ. Bạn muốn đạt được độ tin cậy tối đa có thể của kế hoạch phòng thủ.

Input

  • Dòng đầu tiên của đầu vào chứa ba số nguyên ~n, r~ và ~k~ ~(1 \le n \le 500 000, 0 \le r \le n, 0 \le k \le 10^{18})~ - số phần của bức tường, khoảng cách tối đa đến phần khác cung thủ vẫn có thể bắn và số lượng cung thủ chưa được phân bố dọc theo bức tường.
  • Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n ( 0 \le a_i \le 10^9)~ - số lượng cung thủ hiện tại ở mỗi phần.
  • Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n ( a_i \le b_i \le 2 \times 10^{18})~ - sức chữa tối đa ở mỗi phần.

Output

  • In một số nguyên - giá trị tối đa có thể có của độ tin cậy của kế hoạch phòng thủ, tức là giá trị lớn nhất có thể có của cấp phòng thủ tối thiểu nếu chúng ta phân phối tối ưu ~k~ cung thủ bổ sung

Scoring

  • Subtask 1: (32 %) ~n \le 5000~
  • Subtask 2: (28 %) ~b[i] = 2 \times 10^{18}~
  • Subtask 3: (40 %) ~n \le 500000~

Example

Sample input

8 2 100
0 1 0 1 2 0 0 3
10 13 15 21 17 26 42 31

Sample output

38

Đếm số chính phương

Kuroo

Cho hai số nguyên dương ~L, R~. Đếm xem có bao nhiêu số chính phương trong đoạn ~[L, R]~.

Input: Gồm 1 dòng có 2 số nguyên dương ~L, R \ (1 \leq L \leq R \leq 10^{18})~.

Output: In ra số lượng số chính phương trong đoạn ~[L, R]~.

Ví dụ

Input

1 9

Output

3