Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P165PROB - ROUND 5B - Trồng cây

Tại Học viện Hoàng gia PTIT, có 1 clb mới nổi và thu hút rất nhiếu sự quan tâm của các bạn trẻ. Đó chính là CLB Cây cối. Thu là 1 người năng nổ, cô tham gia ở mọi CLB mà cô cảm thấy thích thú, và CLB Cây cối không phải ngoại lệ. Ngay khi nghe tin CLB tuyển thành viên, Thu đã lập tức nộp đơn đăng ký.

Thu đã xuất sắc vượt qua vòng phỏng vấn để đến vòng test IQ, nếu Thu vượt qua bài test này, cô ấy sẽ trở thành thành viên chính thức của CLB Cây cối. Hãy giúp Thu hoàn thành bài test này nhé:

Cho n cây thuộc m loài cây khác nhau, xếp trên 1 đường thẳng. Cây thứ i sẽ có thông số t[i] và x[i] trong đó t[i] là loài cây (1 <= t[i] <= m), x[i] là tọa độ kiểu số thực của cây tương ứng trên trục tọa độ. Hãy di chuyển các cây sao cho các cây cùng loài luôn đứng cạnh nhau, và từ trái sang phải trên trục tọa độ, chỉ số của loài cây sẽ tăng dần từ 1 đến m. Biết mỗi lần di chuyển là lấy 1 cây và đặt nó vào 1 vị trí bất kì trên trục tọa độ. Hãy xác định số lần di chuyển ít nhất để thỏa mãn yêu cầu trên.

Input

Dòng đầu tiên nhập 2 số tự nhiên n và m (1 <= m <= n <= 5000). Trong đó n là số cây, m là số loài cây.

n dòng tiếp theo, mỗi dòng nhậpsố tự nhiên t[i] và số thực x[i] (1 <= t[i] <= m, 0 <= x[i] <= 109). Trong đó t[i] là chỉ số của loài cây thứ i, x[i] là tọa độ cây thứ i.

Output

In ra số lần di chuyển cây nhỏ nhất.

Example

Test 1:

Input:

1 1

1 0

 

Output:

0

 

Test 2:

Input:

3 3

1 5.0

2 5.5

3 6.0

 

Output:

0

 

Test 3:

Input:

5 5

5 0.2

4 1.2

3 2.2

2 3.2

1 4.2

 

Output:

4


Được gửi lên bởi:adm
Ngày:2016-03-25
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2016-07-14 12:42:06
QHĐ :/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.