Số nguyên dương ~d~ được gọi là ước của số nguyên dương ~N~ nếu ~N~ chia hết cho ~d~. Ví dụ: các ước của ~9~ là ~1, 3~ và ~9;~ các ước của ~10~ là ~1, 2, 5~ và ~10~.

Yêu cầu: Cho hai số nguyên dương ~L~ và ~R~ ~(L ≤ R)~. Hãy tính tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~ ~(~bao gồm cả ~L~ và ~R)~.

Dữ liệu vào từ tệp văn bản SUMDIV.INP:

Gồm một dòng chứa hai số nguyên dương ~L~ và ~R~ ~(1 ≤ L ≤ R ≤ 10^9).~

Kết quả ghi ra tệp văn bản SUMDIV.OUT:

Một số nguyên duy nhất là tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~.

Ràng buộc

• Có ~20\%~ số test ứng với ~R ≤ 1000~;
• ~25\%~ số test khác ứng với ~R - L ≤ 1000~;
• ~25\%~ số test khác ứng với ~R ≤ 10^6~;
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

9 12

Output

63

Giải thích

Các số là ước của ít nhất một số trong đoạn ~[9, 12]~ là: ~1, 2, 3, 4, 5, 6, 9, 10, 11~ và ~12~ ~(7~ và ~8~ không nằm trong danh sách này vì cả ~9, 10, 11~ và ~12~ đều không chia hết cho ~7~ hoặc ~8)~.

Ta có ~1 + 2 + 3 + 4 + 5 + 6 + 9 + 10 + 11 + 12 = 63~.

Input

7 7

Output

8

Giải thích

Các số là ước của ~7~ là ~1~ và ~7~. Ta có ~1 + 7 = 8~.

Tí và Tèo rất thích chơi đùa với những viên ngọc. Hôm nay hai bạn có n viên ngọc trên bàn. Như vạn vật trên đời, mỗi viên ngọc có một vẻ đẹp riêng trong mắt mỗi người. Vì vậy, để giữ tình bạn thân thiết, Tí Tèo quyết định rằng, viên ngọc thứ ~i~ sẽ có vẻ đẹp ~a_i~ đối với Tí và ~b_i~ đối với Tèo. Tí và Tèo bắt đầu trò chơi như sau: hai bạn sẽ thay phiên bốc một viên ngọc trên bàn về phía mình. Sau khi bốc hết ngọc, điểm số của mỗi bạn sẽ là tổng vẻ đẹp các viên ngọc mà bạn đó lấy về phần mình.

Ví dụ nếu Tí bốc các viên 1, 3 và Tèo bốc các viên 2, 4 thì Tí được ~a_1+a_3~ điểm còn Tèo được ~b_2+b_4~ điểm. Mục tiêu của trò chơi là làm cho tổng điểm của mình trừ tổng điểm đối phương càng lớn càng tốt. Nói cách khác, đặt ~X~ là tổng điểm của Tí trừ tổng điểm của Tèo. Tí muốn ~X~ càng lớn càng tốt, còn Tèo muốn ~X~ càng nhỏ càng tốt. Biết rằng Tí đi trước và cả hai đều chơi tối ưu.

Yêu cầu: Hãy tính tổng điểm của Tí trừ tổng điểm của Tèo sau khi trò chơi kết thúc.

Input

• Dòng 1 chứa số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,…,a_n~.
• Dòng thứ ba chứa ~n~ số nguyên ~b_1,b_2,…,b_n~.

Output

• Ghi ra số nguyên là kết quả bài toán.

Constraints

• ~1\leq n\leq 10^5~
• ~0\leq a_i\leq 10^9~ với ~1\leq i\leq n~
• ~0\leq b_i\leq 10^9~ với ~1\leq i\leq n~

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~a_i=b_i~ với mọi ~1\leq i\leq n~.
• Subtask ~2~ (~40\%~ số điểm): ~n\leq 20~.
• Subtask ~3~ (~20\%~ số điểm): ~n\leq 10^3~.
• Subtask ~4~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3
10 20 30
10 20 30 

Sample Output 1

20

Sample Input 2

2
10 20
20 10  

Sample Output 2

0

Sample Input 3

4
10 10 10 20
20 20 20 30 

Sample Output 3

-10

Explanation

• Trong ví dụ 1, Tí bốc viên ngọc thứ 3 trước. Sau đó Tèo bốc viên thứ 2 rồi Tí bốc viên thứ 1 còn lại. Như vậy Tí được ~40~ điểm, còn Tèo được ~20~ điểm. Hiệu là ~20~.
• Trong ví dụ 2, dù Tí bốc viên thứ 1 hay thứ 2 thì hai bạn cũng sẽ bằng điểm nhau.
• Trong ví dụ 3, Tí bốc viên thứ 4 trước. Tèo bốc viên thứ 3. Tí bốc viên thứ 2 rồi Tèo bốc viên thứ 1. Hiệu của 2 bạn là: ~(20 + 10) - (20 + 20) = -10~.

Trong thành phố có ~N~ trạm tiếp sóng. Trên bản thiết kế xây dựng, trạm thứ ~i~ có tọa độ là ~(x_i, y_i)~. Giữa hai trạm ~i~ và ~j~, chi phí để liên kết hai trạm này với nhau là ~\min(|x_i − x_j|, |y_i − y_j|)~. Lãnh đạo thành phố muốn liên kết toàn bộ các trạm tiếp sóng với nhau (hai trạm được gọi là có liên kết với nhau khi chúng có liên kết trực tiếp với nhau hoặc liên kết qua một số trạm trung gian khác).

Yêu cầu: Hãy giúp lãnh đạo thành phố tính tổng chi phí nhỏ nhất để liên kết toàn bộ ~N~ trạm tiếp sóng.

Dữ liệu vào từ tệp văn bản BTS.INP:

• Dòng đầu tiên ghi số nguyên ~N~ ~(2 ≤ N ≤ 10^5)~ là số trạm tiếp sóng;
• ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~x_i~ và ~y_i~ ~(1 ≤ i ≤ N~; ~\ 1 ≤ x_i ≤ 10^9~; ~\ 1 ≤ y_i ≤ 10^9)~ là tọa độ của trạm tiếp sóng thứ ~i~.

Kết quả ghi ra tệp văn bản BTS.OUT:

Một số nguyên duy nhất là tổng chi phí nhỏ nhất để liên kết các trạm tiếp sóng trên.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 10^3~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

5
4 9
9 5
0 2
7 1
3 4

Output

5

Giải thích

• Liên kết giữa trạm ~2~ và ~4~ với chi phí ~2~.
• Liên kết giữa trạm ~3~ và ~4~ với chi phí ~1~.
• Liên kết giữa trạm ~2~ và ~5~ với chi phí ~1~.
• Liên kết giữa trạm ~1~ và ~5~ với chi phí ~1~.

Tổng chi phí sẽ là: ~2 + 1 + 1 + 1 = 5~.

Trên hệ trục tọa độ ~OXY~, có ~n~ con robot, con robot thứ ~i~ ở tọa độ ~(x_i,y_i)~.

Giả sử một con robot đang ở vị trí ~(x,y)~, sau một giây, nó có thể đi tới ~4~ vị trí ~(x-1,y)~, ~(x,y-1)~, ~(x+1,y)~, ~(x,y+1)~.

Hãy tìm thời điểm ngắn nhất sao cho cả ~n~ con robot đều có thể cùng đứng ở một điểm nào đó trên hệ trục tọa độ.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ miêu tả số robot ~(1 \le n \le 3\times 10^5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của robot thứ ~i~ ~(|x_i|,|y_i| \le 10^{18})~.

Output

• In ra thời điểm nhanh nhất để các robot cùng đứng tại một điểm.

Sample Input 1

3
0 0
0 3
3 3

Sample Output 1

3

Cho dãy số nguyên dương ~a[1], a[2], …, a[N]~. Xét cách chia dãy số ~a~ thành ~K~ nhóm sao cho mỗi nhóm chứa một đoạn liên tiếp các phần tử của ~a~. Gọi trọng số của một cách chia là tổng các phần tử lớn nhất của mỗi nhóm

Yêu cầu: Tìm cách chia dãy số ~a~ thành ~K~ nhóm sao cho trọng số của cách chia là nhỏ nhất

Dữ liệu

• Dòng 1: 2 số nguyên dương ~N~ và ~K~ (~K \le N~)
• Dòng 2: Gồm ~N~ số nguyên dương ~a[1], a[2], …, a[N]~

Kết quả:

• Ghi ra 1 số nguyên duy nhất là trọng số tìm được

Input 1

    5 1
    1 2 3 4 5   

Output 1

    5

Input 2

    5 2
    1 2 3 4 5   

Output 2

``` 6

Giới hạn:

• 14% số điểm: ~1\le N\le100, K\le min(N, 5)~
• 18% số điểm: ~1\le N\le20~
• 21% số điểm: ~1\le N\le100~
• 47% số điểm: ~1\le N\le100000, K\le min(N, 100).~