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.|

C11DK1 - Những chiếc lá mùa thu

“Hà Nội mùa thu, cây cơm nguội vàng, cây bàng lá đỏ, nằm kề bên nhau phố xưa nhà cổ, mái ngói thâm nâu. ... Hà Nội mùa thu! Đi giữa mọi người, lòng như thầm hỏi "tôi đang nhớ ai?", sẽ có một ngày trời thu Hà Nội, trả lời cho tôi, sẽ có một ngày từng con đường nhỏ trả lời cho tôi.”

 


 Ngày 7-10-2011, khaihanhdk tặng ĐK

Mỗi năm đến mùa thu, những chiếc lá vàng lại rơi khắp trên đường làng, nơi mà khaihanhdk đang ở. Do lần đầu tiên xếp hạng cuối lớp, thầy chủ nhiệm đã phạt khaihanhdk phải quét hết lá vàng rơi trên con đường làng trước ngày 7-10. Nhưng đã học tệ rồi, lại còn thêm tính lười biếng. Cuối cùng, ngày 6-10 cũng đã đến, nhưng khaihanhdk vẫn chưa quét được chiếc lá vàng nào, khaihanhdk cứ ngồi khóc mãi, khóc mãi. Bỗng một lúc sau, Bụt hiện ra và hỏi: “Kìa con, vì sao con khóc?”.

Khaihanhdk kể lại hết câu chuyện cho Bụt nghe, Bụt nói: “Ờ, ta hiểu rồi, ta chỉ có một cách để giúp con. Con hãy ra cửa hàng Olympic Tin học Việt Nam (VNOI), con mua vài chiếc máy hút lá vàng do cựu học sinh Nguyễn Vương Linh vừa đem hàng từ Thái Lan về. Vấn đề bây giờ là con phải biết cách chọn lựa máy nào cho tốt mà ít tốn kém đấy nhé. Nếu con không biết có thể hỏi các coder trên trang web vnoi.info, có thể họ sẽ có cách giúp con. Thôi, ta đi đây.”

Con đường làng là 1 đường thẳng, trên đó mỗi chiếc lá vàng có tọa độ x[i], có không quá n (n <= 10^4) chiếc lá vàng trên đường.

Cửa hàng có m (m <= 10^4) loại máy, có thể mua nhiều cái máy cùng 1 loại, không giới hạn số lượng. Mỗi loại máy có 2 thông số là:

            d[i]: nếu đặt máy i ở vị trí x thì nó sẽ hút được tất cả các lá vàng có tọa độ nằm trong khoảng [x – d[i], x + d[i]].

            c[i]: chi phí để mua máy.

Yêu cầu: Cần đặt một số máy lên đường làng sao cho các máy hút hết được lá vàng và chi phí mua máy là thấp nhất.

Input

            Dòng đầu gồm 2 số: n và m.

            N dòng tiếp theo: mỗi dòng ghi số x[i] (abs(x[i]) <= 10^9).

            M dòng tiếp thep: mỗi dòng ghi 2 số: d[i] và c[i] (1 <= d[i] <= 10^9, c[i] <= 1000).

Output

            Chi phí nhỏ nhất tìm được.

Example

Input:

5 3

2

8

3

6

9

7 9

2 3

8 6

Output:

 


Được gửi lên bởi:Nguyễn Duy Khánh
Ngày:2011-10-06
Thời gian chạy:0.605s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC GAWK MAWK BC C-CLANG C CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PROLOG PY_NBC R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Nguồn bài:Ý tưởng chưa có lời giải

hide comments
2017-11-12 10:06:12
oh yeah, sảng khoái quá, mình nghĩ mình k thể làm được bài này cơ, thanh bác comment cuối nhé ^^
{dinh truong lam}
2016-09-27 03:35:58
Code:
http://shink.in/3hTzR
2014-07-10 17:41:21 Lollipop
Code lòi mắt mới Ac, toàn TLE :))

Last edit: 2014-07-10 18:10:46
2014-07-01 10:56:52 Tây Cuồng
Mặc dù đã ac nhưng thời gian chạy là 10.7s, không biết anh (chị) Bit với anh (chị) Cottontail Tee làm cách nào mà chương trình chạy nhanh thế nhỉ?

Last edit: 2014-07-01 10:57:37
2014-06-30 21:07:48 Nắng
đpt >10^8 vẫn AC :D may quá ^^
2013-06-05 09:23:32 an IM3 Ex-Member of Bit
QHD 10^7 --> AC :D
2013-06-04 06:03:24 Cottontail Tee
chú ý giới hạn c[i] là AC :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.