Để tạo không khí vui vẻ náo nhiệt, trong buổi giao lưu giữa sinh viên các trường tham dự OLP-ACM, trường đăng cai OLP năm tới đề xuất tổ chức một cuộc thi đấu game online tay đôi giữa sinh viên trường mình và sinh viên trường sở tại. Mỗi trường cử ra một đội n người, tạo thành n cặp đấu, sinh viên cùng trường không đấu với nhau. Trò chơi được chọn là một trò chơi phổ biến và được nhiều bạn trẻ yêu thích, ai cũng biết và chơi nhiều trước đó.

Mọi người đều biết chỉ số năng lực của mình và khi đấu tay đôi thì ai có chỉ số năng lực cao hơn sẽ thắng. Trong các trận đấu tay đôi, người thắng sẽ được 1 điểm, người thua được 0 điểm. Thời gian chơi được quy định đủ để phân biệt thắng thua. Các trận hòa sẽ kéo dài vô hạn sẽ bị hủy kết quả khi hết thời gian.

Với tinh thần fairplay các bạn trường đề xuất ngồi vào vị trí thi đấu, truy cập vào hệ thống và gửi về máy chủ chỉ số năng lực của mình. Trưởng đoàn của trường sở tại có 1 giây để xử lý thông tin, phân công ai đấu với ai để tổng số điểm thu được là lớn nhất.

Yêu cầu : Hãy xác định với cách bố trí tối ưu các cặp đấu, đội của trường sở tại sẽ có bao nhiêu điểm?

Đầu vào

• Dòng đầu chứa n

• Dòng thứ hai chứa n số nguyên a1, a2, ... an trong đó a[i] là chỉ số năng lực của người thứ i thuộc đội của trường đề xuất.

• Dòng thứ 3 chứa n số nguyên b1, b2, ...bn trong đó b[i] là chỉ số năng lực của người thứ i thuộc đội trường sở tại.

Giới hạn

• 1 ≤ n ≤ 100000

• 1 ≤ a[i] <= 10^9

• 1 ≤ b[i] <= 10^9

Đầu ra

Là một số nguyên duy nhất xác định số điểm đội trường sở tại có thể đạt được với cách bố trí cặp chơi tối ưu.

Ví dụ :

Input 01

5
10 15 30 20 25
28 24 20 16 14

Output 01

4

Trong một hội nghị do thành phố tổ chức, các con đường được trang trí bởi các chậu hoa, mỗi chậu hoa có 1 màu sắc khác nhau. Khi đi tham dự, Nam và Lan nhìn thấy một dãy n chậu hoa được đặt cách nhau đều đặn và được đánh số 1, 2, 3... n. Hai bạn quan sát và nhận ra rằng có tất cả m màu hoa khác nhau, để đơn giản có thể coi một màu trên chậu hoa là một số nguyên dương.

Là một người yêu hoa, Lan muốn chụp một bức ảnh trong đó phải có đủ m màu hoa, tất nhiên trong ảnh các chậu hoa phải liên tiếp nhau. Để ảnh được rõ nét, Lan muốn số chậu hoa xuất hiện trong ảnh là ít nhất. Nam quan sát và khá bối rối, bạn hãy giúp Nam giải quyết vấn đề mà Lan đặt ra và cho biết rằng trong bức ảnh có bao nhiêu chậu hoa xuất hiện.

Đầu vào

• Dòng đầu chứa n và m

• Dòng thứ hai chứa n số nguyên a1, a2, ... an

Giới hạn

• 1 ≤ m ≤ n ≤ 1000000

• 1 ≤ a[i] <= 10^6

Đầu ra

In ra số lượng chậu hoa có trong bức ảnh.

Ví dụ :

Input 01

8 3
1 1 2 2 1 1 3 3

Output 01

4

Giải thích test :

Nam chụp bức ảnh gồm 4 chậu 4, 5, 6, 7

Ngày nay việc mua bán trực tuyến trở nên phổ biến, chúng ta có thể các sản phẩm thông qua các kênh bán hàng trực tuyến sau đó các đơn vị vận chuyển sẽ giao hàng tận nhà.

Một đơn vị vận chuyển có n trung tâm trung chuyển được đánh số từ 1 đến n. Giữa hai trung tâm trung chuyển được nối tối đa bởi 1 tuyến đường 2 chiều. Có tất cả m tuyến đường, tuyến đường thứ i nối giữa 2 trung tâm a[i] và b[i] có khoảng cách là c[i] (i = 1, 2, ...m)

Yêu cầu : Hãy xác định tổng khoảng cách ngắn nhất để vận chuyển một kiện hàng từ trung tâm trung chuyển s đến trung tâm trung chuyển t.

Đầu vào

• Dòng đầu chứa 4 số nguyên n, m, s, t

• Dòng thứ i trong m dòng tiếp theo ghi 3 số a[i], b[i], c[i], a[i] khác b[i]

Giới hạn

• 1 ≤ s, t ≤ n ≤ 100000, s khác t

• 1 ≤ m ≤ 100000

• 0 ≤ c[i] <= 10^9

Đầu ra

In ra khoảng cách ngắn nhất tìm được

Ví dụ :

Input 01

5 7 1 5
1 2 3
1 4 8
2 3 5
2 4 4
3 5 5
4 3 8
4 5 3

Output 01

10