Cho dãy số nguyên A gồm N phần tử, một dãy con liên tiếp của A được gọi là tốt khi tổng các phần tử của dãy bằng độ dài của dãy đó. Ví dụ: ~A = [1,0,2]~ thì sẽ có 3 dãy con tốt là ~[1], [0,2], [1,0,2]~

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương N. ~(N \le 10^5)~
• Dòng thứ hai chứa N phần tử ~a_i~ ~(|a_i | \le 10^9)~

Kết quả

Chứa 1 số duy nhất là kết quả bài toán.

Ví dụ

Dữ liệu 1

3
1 0 2

Kết quả 1

3

Dữ liệu 2

6
6 0 0 0 0 5

Kết quả 2

1

Ràng buộc

• Có 50% số điểm của bài tương ứng với N <= 100.
• Có 25% số điểm của bài tương ứng với N <= 1000.
• Có 25% số điểm của bài tương ứng với ràng buộc đề bài.

Minh là một người rất yêu thích số nguyên tố, đồng thời cậu cũng rất thích số 5. Do đó, cậu ta luôn coi những số nguyên tố có tổng các chữ số chia hết cho 5 là số đặc biệt. Lần này, thầy giáo cho Minh hai số nguyên dương ~L,R (L≤R)~ và muốn Minh cho biết trong đoạn [L,R] có bao nhiêu số đặc biệt. Bạn hãy lập trình tìm câu trả lời giúp Minh.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~T≤10^5~ là số lượng cặp số nguyên ~L,R~ cần trả lời;
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L,R~ ~(0<L≤R≤ (3×10)^6)~ phân biệt nhau bởi một dấu cách</li>

Kết quả

Gồm T dòng, mỗi dòng ghi một số nguyên là số lượng số đặc biệt trong đoạn ~[L,R]~ tương ứng với thứ tự dữ liệu đầu vào.

Ví dụ

Dữ liệu 1

2
1 10
4 20

Kết quả 1

1
2

Giải thích: Đoạn [1,10] có 1 số đặc biệt là 5, đoạn [4,20] có 2 số đặc biệt là 5 và 19.

Ràng buộc

• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: T=1;0<L,R≤10^3;</li>
• 30% số test khác ứng với 30% số điểm của bài thỏa mãn: 2≤T≤10; 0<L,R≤10^5;</li>
• 30% số test còn lại ứng với 30% số điểm của bài thỏa mãn: T≤10^5; 0<L,R≤〖3×10〗^6;</li>

An có một mảng a gồm n số nguyên phân biệt. Bình lấy đúng ~n-1~ phần tử từ mảng ~a~ và cộng thêm cho mỗi phần tử này một số nguyên dương ~x~, sau đó xáo trộn chúng để tạo thành một mảng mới ~b~ có ~n-1~ phần tử. Cho hai mảng ~a~ và ~b~, bạn hãy xác định giá trị ~x~ mà Bình đã chọn. Nếu có nhiều giá trị ~x~ thỏa mãn, thì hãy đưa ra giá trị nhỏ nhất trong số chúng.

Dữ liệu

Dòng đầu tiên chứa số nguyên ~t~ ~(1≤t≤5)~ là số test. Các dòng tiếp theo mô tả ~t~ test, mỗi test mô tả trên ~3~ dòng:

• Dòng đầu tiên của mỗi test chứa số nguyên ~n~ ~(2≤n≤10^5 )~ là số phần tử của mảng ~a~;
• Dòng thứ hai của mỗi test chứa n số nguyên phân biệt ~a_1,a_2,…,a_n~ ~(1≤a_i≤10^9 )~ là các phần tử của mảng ~a~;
• Dòng thứ ba của mỗi test chứa ~n-1~ số nguyên phân biệt ~b_1,b_2,…,b_(n-1)~ ~(1≤b_i≤2×10^9)~ là các phần tử của mảng ~b~.

Kết quả

Với mỗi test, in ra giá trị ~x~ mà Bình đã chọn. Trường hợp có nhiều giá trị x thỏa mãn, hãy in giá trị nhỏ nhất trong số chúng. Dữ liệu cho đảm bảo rằng luôn tồn tại ít nhất một giá trị ~x~.

Ví dụ

Dữ liệu 1

3
4
1 4 3 8
15 8 11
2
4 8
10
2
2 4
3

Kết quả 1

7
2
1

Giải thích: Trong test thứ nhất, Bình lấy các phần tử 1,4,8 và cộng thêm 7 vào mỗi phần tử này được mảng 8,11,15, sau đó anh ta xáo trộn chúng để có được mảng b mới là 15,8,11. Không có giá trị x nào khác thỏa mãn yêu cầu bài toán. Trong test thứ hai có 2 lựa chọn với Bình để xem xét: một là lấy phần tử 4 và cộng thêm 6 vào nó để được mảng b; hai là lấy phần tử 8 và cộng thêm 2 vào nó để được mảng b. Nhưng giá trị 2 là nhỏ nhất trong số các giá trị x thỏa mãn, do đó câu trả lời là 2. Trong test thứ ba chỉ có một lựa chọn với Bình để xem xét là lấy phần tử 2 và cộng thêm 1 vào nó để được mảng b. Nếu anh ta lấy phần tử 4 thì anh ta sẽ phải cộng thêm -1 vào phần tử này, nhưng giá trị cộng thêm này không dương nên việc cộng này là không hợp lệ.

Ràng buộc

• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: ~t=1~ và ~2≤n≤10~;
• 25% số test khác ứng với 25% số điểm của bài thỏa mãn: ~2≤n≤10^2~; ~1≤a_i≤10^4~ và ~1≤b_i≤2×10^4~;
• 25% số test khác ứng với 25% số điểm của bài thỏa mãn: ~2≤n≤10^3~;
• 25% số test còn lại ứng với 25% số điểm của bài không có thêm ràng buộc nào.

Để chuẩn bị cho hội thi Tin học trẻ sắp tới, thầy giáo quyết định giao một bộ đề thi gồm N đề thi khác nhau cho Minh để tự luyện tập. Các đề thi được đánh số từ 1 đến N, mỗi đề thi sẽ giúp rèn luyện một số kỹ năng cho Minh để có thể đạt thành tích tốt trong hội thi Tin học trẻ. Nhằm định hướng cho quá trình luyện tập đạt hiệu quả cao nhất, mỗi đề thi có một yêu cầu tối thiểu về trình độ kỹ năng. Để giải được đề thi i, Minh cần có trình độ kỹ năng tối thiểu là ai. Điều này có nghĩa là Minh có thể giải được đề thi thứ i khi và chỉ khi có trình độ kỹ năng bằng hoặc lớn hơn ai. Nếu giải được đề thi i thì trình độ kỹ năng của Minh sẽ tăng thêm một lượng là b_i. Giả sử ban đầu, trình độ kỹ năng của Minh trước khi luyện tập là c. Các đề thi có thể được giải theo trình tự bất kỳ.

Yêu cầu: Cho các số nguyên N,c và các cặp giá trị ~(a_i,b_i )~, hãy xác định số lượng đề thi tối đa mà Minh có thể giải được.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~N,c~ ~(1 \le N \le 10^5, 0 \le c \le 10^9 )~;
• Dòng thứ i trong N dòng tiếp theo ~(1 \le i \le N)~ chứa 2 số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i,b_i \le 10^9 )~. Các số trên cùng một dòng được phân cách nhau bởi một dấu cách.

Kết quả

Một số nguyên dương, là số đề thi tối đa mà Minh có thể giải được.

Ví dụ

Dữ liệu 1

4 1
1 10
21 5
1 10
100 100

Kết quả 1

3

Giải thích: Với N=4,c =1 và các cặp giá trị ~(a_i,b_i )~ tương ứng là ~(1,10), (21,5), (1,10), (100,100)~, Minh sẽ giải đề thi 1 sau đó giải đề thi 3 và cuối cùng giải đề thi 2. Đề thi 4 Minh không giải được vì không đủ kỹ năng. Như vậy, Minh giải được tối đa 3 đề thi.

Ràng buộc

• Có 60% số test ứng với 60% số điểm của bài thỏa mãn: ~N \le 1000~, ~(1 \le a_i,b_i \le 10^5 )~;
• 40% số test còn lại ứng với 40% số điểm của bài không có thêm ràng buộc nào.