Trong danh sách bạn bè của Jessie, có rất nhiều người có chung 1 ngày sinh nhật. Vào ngày này, $N$ tiệc sinh nhật được tổ chức tại $N$ ngôi nhà nằm dọc theo một tuyến phố. Các ngôi nhà được đánh số theo thứ tự từ $1$ đến $N$. Và khoảng cách từ ngôi nhà $i$ đến ngôi nhà $i+1$ là $D_i$.
Jessie đã mua được $M$ món quà hot trend để tặng cho những người bạn có sinh nhật trong ngày hôm nay. Nhưng vì có quá nhiều người bạn nên cô không biết sẽ tặng món quà nào cho từng bạn. Theo quan sát của Jessie, mỗi người bạn sẽ có độ yêu thích khác nhau cho từng món quà. Người bạn $i$ sẽ có độ yêu thích là $C_{ij}$ cho món quà thứ $j$. Mỗi món quà chỉ được tặng cho 1 bạn duy nhất, nhưng mỗi bạn có thể nhận nhiều món quà khác nhau.
Jessie muốn tặng hết $M$ món quà. Xuất phát từ một ngôi nhà tùy thích, tại mỗi ngôi nhà, cô sẽ chọn một số món quà sinh nhật để tặng cho người bạn tại đây rồi di chuyển đến ngôi nhà khác. Để đánh giá một ngày đi ăn sinh nhật thành công, Jessie sử dụng công thức sau để xác định độ hài lòng: <Tổng độ yêu thích khi tặng các món quà> - <Tổng độ dài đoạn đường phải di chuyển>. Trong đó, tổng độ dài di chuyển được tính từ thời điểm xuất phát đến thời điểm tặng quà cho ngôi nhà cuối cùng. Hãy xác định độ hài lòng tối đa mà Jessie có thể đạt được.
Lưu ý rằng do quỹ tiết kiệm có hạn nên Jessie có thể bỏ qua và không tặng quà cho một số người bạn của mình.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ $(1 \le N \le 5\,000, 1 \le M \le 200)$ - số lượng người bạn có sinh nhật vào cùng ngày, và số lượng món quà mà Jessie đã chuẩn bị.
- Dòng thứ hai gồm $N-1$ số nguyên ~D_1, D_2, \dots, D_{N-1}~ ~(1 \le D_i \le 10^9)~- khoảng cách giữa các ngôi nhà trên tuyến phố.
- $N$ dòng tiếp theo, dòng thứ $i$ gồm $M$ số nguyên ~C_{i1}, C_{i2}, \dots, C_{iM}~ ~(1 \le C_{ij} \le 10^9)~ - độ yêu thích món quà $j$ ~(1 \le j \le M)~ của người thứ $i$.
Kết quả
Gồm một dòng duy nhất là độ hài lòng tối đa của chuyến đi dự sinh nhật của Jessie.
Giới hạn
- Subtask $1$ $(20\%)$: $N \le 80$;
- Subtask $2$ $(20\%)$: $N \le 500$;
- Subtask $3$ $(10\%)$: $M = 1$;
- Subtask $4$ $(20\%)$: $M \le 10$;
- Subtask $4$ $(30\%)$: Không có ràng buộc gì thêm.
Ví dụ 1
Dữ liệu
3 4
1 4
2 2 5 1
1 3 3 2
2 2 5 1
Kết quả
11
Giải thích
Jessie xuất phát tại ngôi nhà $1$, tặng món quà $1$ và $3$. Sau đó di chuyển đến ngôi nhà $2$, và tặng món quà $2$ và $4$. Độ hài lòng của Jessie là $2+5+3+2-1 =11$
Ví dụ 2
Dữ liệu
5 3
1 2 3 4
10 1 1
1 1 1
1 10 1
1 1 1
1 1 10
Kết quả
20
Bình luận