Bài tập

Bạn Nam là một tay vợt cầu lông chuyên nghiệp. Trong năm có \(n\) giải đấu, giải thứ \(i\) diễn ra vào ngày \(a_i\) và mang lại tiền thưởng \(b_i\) cho người tham gia. Để giữ sức khoẻ, huấn luyện viên yêu cầu hai giải mà Nam đăng ký phải cách nhau ít nhất \(k\) ngày, tức là với hai giải \(i \ne j\) được chọn thì \(|a_i - a_j| \ge k\).

Hãy chọn một tập giải đấu thoả yêu cầu sao cho tổng tiền thưởng là lớn nhất và in ra tổng đó.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1 < a_2 < \dots < a_n\) là ngày diễn ra các giải.
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n\) là tiền thưởng của các giải.

Output

In ra một số nguyên là tổng tiền thưởng lớn nhất có thể nhận được.

Constraints

• \(1 \le n \le 100\), \(1 \le k \le 10\)
• \(1 \le a_i \le 365\)
• \(1 \le b_i \le 10^9\)

Sample Input 1

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

Sample Output 1

24

Sample Input 2

4 30
5 10 20 40
8 3 9 1

Sample Output 2

9

Explanation

Ở ví dụ 1 chọn các ngày \(2, 5, 9, 12\) (cách nhau ít nhất 3 ngày): \(7+6+10+1=24\). Ở ví dụ 2, \(k=30\) nên chỉ chọn được ngày 5 và 40 (tổng 9) hoặc riêng ngày 20 (tổng 9).

Một trung tâm ngoại ngữ mở \(N\) buổi học ngoại khoá, buổi thứ \(i\) diễn ra từ thời điểm \(S_i\) đến thời điểm \(E_i\). Bạn Lan muốn tham gia một số buổi trong đó, nhưng không muốn bị trùng giờ.

Hai buổi học được gọi là xếp được cùng nhau nếu buổi này kết thúc không muộn hơn thời điểm buổi kia bắt đầu (buổi này kết thúc đúng lúc buổi kia bắt đầu vẫn hợp lệ). Một tập các buổi học là hợp lệ nếu mọi cặp buổi trong tập đều xếp được cùng nhau. Tập rỗng không được tính.

Hãy đếm số tập khác rỗng các buổi học hợp lệ. Hai tập khác nhau nếu chúng chứa những chỉ số buổi học khác nhau (hai buổi có cùng \(S, E\) vẫn được xem là hai buổi khác nhau).

Vì đáp số có thể rất lớn nên chỉ in ra 8 chữ số cuối cùng của kết quả; nếu kết quả có ít hơn 8 chữ số thì thêm các chữ số \(0\) vào đầu cho đủ 8 chữ số.

Input

Dữ liệu gồm nhiều bộ test, kết thúc bằng một dòng chứa \(-1\). Mỗi bộ test gồm:

• Dòng đầu chứa số nguyên \(N\) là số buổi học.
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(S\) và \(E\) là thời điểm bắt đầu và kết thúc của một buổi.

Output

Với mỗi bộ test, in ra một dòng gồm đúng 8 chữ số là 8 chữ số cuối của số tập hợp lệ (có thể có các số \(0\) ở đầu).

Constraints

• Số bộ test không quá \(5\).
• \(1 \le N \le 10^5\)
• \(1 \le S \le E \le 10^9\) (một buổi có thể có độ dài \(0\))

Sample Input

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

Sample Output

00000015
00000007
00000002

Explanation

Bộ test thứ hai: ba buổi đều là \([7,7]\) (độ dài \(0\)), đôi một xếp được cùng nhau nên mọi tập khác rỗng đều hợp lệ: \(2^3-1=7\). Bộ test thứ ba: hai buổi lồng nhau nên chỉ chọn được từng buổi một, có \(2\) tập.

Một trung tâm ngoại ngữ mở \(N\) buổi học ngoại khoá, buổi thứ \(i\) diễn ra từ thời điểm \(S_i\) đến thời điểm \(E_i\). Bạn Lan muốn tham gia một số buổi trong đó, nhưng không muốn bị trùng giờ.

Hai buổi học được gọi là xếp được cùng nhau nếu buổi này kết thúc không muộn hơn thời điểm buổi kia bắt đầu (buổi này kết thúc đúng lúc buổi kia bắt đầu vẫn hợp lệ). Một tập các buổi học là hợp lệ nếu mọi cặp buổi trong tập đều xếp được cùng nhau. Tập rỗng không được tính.

Hãy đếm số tập khác rỗng các buổi học hợp lệ. Hai tập khác nhau nếu chúng chứa những chỉ số buổi học khác nhau (hai buổi có cùng \(S, E\) vẫn được xem là hai buổi khác nhau).

Vì đáp số có thể rất lớn nên chỉ in ra 8 chữ số cuối cùng của kết quả; nếu kết quả có ít hơn 8 chữ số thì thêm các chữ số \(0\) vào đầu cho đủ 8 chữ số.

Input

Dữ liệu gồm nhiều bộ test, kết thúc bằng một dòng chứa \(-1\). Mỗi bộ test gồm:

• Dòng đầu chứa số nguyên \(N\) là số buổi học.
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(S\) và \(E\) là thời điểm bắt đầu và kết thúc của một buổi.

Output

Với mỗi bộ test, in ra một dòng gồm đúng 8 chữ số là 8 chữ số cuối của số tập hợp lệ (có thể có các số \(0\) ở đầu).

Constraints

• Số bộ test không quá \(20\).
• \(1 \le N \le 3000\)
• \(1 \le S < E \le 10^9\)

Sample Input

4
1 4
2 3
3 6
4 8
2
5 10
5 10
3
20 30
1 20
1 10
-1

Sample Output

00000007
00000002
00000005

Explanation

Bộ test đầu: có 4 tập một buổi và 3 tập hai buổi hợp lệ là \(\{1,4\}\), \(\{2,3\}\), \(\{2,4\}\) (theo chỉ số), tổng cộng \(7\). Bộ test thứ hai: hai buổi trùng nhau hoàn toàn nên chỉ có 2 tập một buổi. Bộ test thứ ba: buổi 1 \([20,30]\) ghép được với buổi 2 \([1,20]\) và buổi 3 \([1,10]\), còn buổi 2 và 3 trùng nhau, nên có \(3 + 2 = 5\) tập.

Cho ba số nguyên \(m < n < k\). Nếu ba số này theo thứ tự đó lập thành một cấp số cộng (tức là \(n - m = k - n\)) thì in ra tổng của chúng, ngược lại in ra dòng chữ KHONG PHAI CAP SO CONG.

Input

Một dòng chứa ba số nguyên \(m, n, k\).

Output

In ra tổng \(m + n + k\) nếu chúng lập thành cấp số cộng, ngược lại in KHONG PHAI CAP SO CONG.

Constraints

• \(-10^9 \le m < n < k \le 10^9\).

Sample Input 1

4 7 10

Sample Output 1

21

Sample Input 2

2 5 9

Sample Output 2

KHONG PHAI CAP SO CONG