Buôn Bán Giữa Các Hành Tinh

Điểm: 3,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một thương nhân muốn kiếm lời bằng cách mua hàng tại một hành tinh rồi bay sang một hành tinh khác để bán toàn bộ. Việc mua và bán chỉ diễn ra duy nhất một lần.

Hệ có $n$ hành tinh, trên mỗi hành tinh đều bán $m$ loại hàng. Với mỗi hành tinh $i$ và mỗi loại hàng $j$ ta biết:

$a_{i j}$ — giá mua một đơn vị loại $j$ trên hành tinh $i$ ;
$b_{i j}$ — giá bán một đơn vị loại $j$ trên hành tinh $i$ ;
$c_{i j}$ — số đơn vị loại $j$ còn lại trên hành tinh $i$ .

Khi đặt chân lên hành tinh mua, thương nhân không được mua quá $c_{i j}$ đơn vị mỗi loại; còn khi sang hành tinh bán thì có thể bán không giới hạn số lượng cho mỗi loại. Khoang chứa của tàu chỉ chở được tối đa $k$ đơn vị hàng (tổng tất cả các loại).

Hãy xác định lợi nhuận lớn nhất có thể thu được. Lưu ý: thương nhân có quyền không mua gì cả, khi đó lợi nhuận bằng $0$ .

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $m$ , $k$ .
Tiếp theo là n khối mô tả các hành tinh. Khối thứ i gồm:
- Một dòng chứa tên hành tinh (chuỗi từ $1$ đến $10$ chữ cái Latinh, chữ cái đầu viết hoa, các chữ còn lại viết thường).
- $m$ dòng tiếp, dòng thứ $j$ chứa ba số $a_{i j}$ , $b_{i j}$ , $c_{i j}$ .

Tên các hành tinh đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên duy nhất — lợi nhuận lớn nhất.

Ràng buộc

$2 \leq n \leq 10$
$1 \leq m, k \leq 100$
$1 \leq b_{i j} < a_{i j} \leq 1000$
$0 \leq c_{i j} \leq 100$

Ví dụ

Input	Output	Giải thích
3 3 10 Venus 6 5 3 7 6 5 8 6 10 Earth 10 9 0 8 6 4 10 9 3 Mars 4 3 0 8 4 12 7 2 5	16	Bay đến Venus, vay $74$ tiền và mua $3$ đơn vị loại $1$ cùng $7$ đơn vị loại $3$ ( $3 \cdot 6 + 7 \cdot 8 = 74$ ). Bay sang Earth và bán toàn bộ, thu về $3 \cdot 9 + 7 \cdot 9 = 90$ . Trả nợ $74$ , lợi nhuận là $16$ .
2 1 5 A 6 5 5 B 10 9 0	15	Mua $5$ đơn vị tại A với giá $6$ , bán tại B với giá $9$ (B không có hàng nên không thể mua tại B). Lợi nhuận: $5 \cdot (9 - 6) = 15$ .

Bình luận

Không có bình luận tại thời điểm này.