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

IOI2008 - IOI2008

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/ioi2008


IOI 2008 diễn ra trong n + 1 ngày, các bài toán của IOI được đánh số từ 1 tới n.(n+1) và được phân bố vào các ngày thi theo lịch sau (mỗi ngày thi có n bài toán):

Ngày 1: Các bài toán từ 1 tới n

Ngày 2: Các bài toán từ n + 1 tới 2n

...

Ngày i: Các bài toán từ (i - 1).n + 1 tới i.n

...

Ngày n+1: Các bài toán từ n.n + 1 tới n.(n+1)

Các bài thi có một trong k dạng, bài thứ j có dạng là rj (1 <= rj <= k)

Thể thức thi được thông báo cho mỗi đoàn như sau:

- Mỗi đoàn sẽ có n + 1 học sinh tham gia

- Hàng ngày, Ban tổ chức sẽ đưa một học sinh của đoàn đi tham quan thành phố, việc chọn học sinh nào cho đi tham quan là quyền của trưởng đoàn, nhưng phải đảm bảo điều kiện:

Cho đến khi IOI kết thúc, học sinh nào của đoàn cũng đã được đi tham quan thành phố. Như vậy mỗi ngày đoàn sẽ còn lại n học sinh tham gia thi, việc giao cho học sinh nào làm bài nào là quyền của phó đoàn nhưng mỗi học sinh chỉ được giao một bài và hai học sinh khác nhau sẽ phải nhận hai bài khác nhau.

Kết thúc IOI, điểm đồng đội của mỗi đoàn sẽ được tính bằng tổng điểm của tất cả các lời giải các bài toán đã cho.

Các thầy giáo trưởng, phó đoàn Việt Nam dự đoán rằng nếu học sinh thứ i của đoàn làm bài toán dạng j thì có thể thu được số điểm là cij (cij = 0 tương đương với lời dự đoán rằng học sinh thứ i không làm được bài toán dạng j).

Hỏi các thầy sẽ sắp xếp lịch thi đấu cho các học sinh như thế nào để theo dự đoán, đoàn Việt Nam sẽ thu được số điểm nhiều nhất có thể.

Input

Dòng 1: Chứa hai số n, k (1 <= n <= 100; 1 <= k <= 1000)

Dòng 2: Chứa n.(n+1) số, số thứ p là rp.

Các dòng tiếp, mỗi dòng chứa ba số nguyên dương i, j, p cho biết một điều dự đoán của các thầy: học sinh thứ i có thể làm được bài toán dạng j và đạt được số điểm là p (=c[i, j]). (1 <= p <= 100)

Output

Gồm 1 dòng duy nhất : Ghi điểm đồng đội mà theo dự đoán đoàn Việt Nam có thể đạt

Example

Input:
3 4
1 2 4 4 3 3 1 4 2 3 2 2
1 1 2
1 2 3
1 4 6
2 3 4
2 1 3
2 4 7
3 2 1
3 1 4
4 1 2
4 3 9
4 2 8

Output:
65

I hope and expect that you will have much success in IOI 2008 ^^


Được gửi lên bởi:special_one
Ngày:2008-06-13
Thời gian chạy:0.104s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Lê Minh Hoàng

hide comments
2016-08-26 05:25:06
ai muôn code thì hỏi t qua face này https://www.facebook.com/huynhduy.idol?fref=ts
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.