Như ta đã biết, nàng Bạch Tuyết xinh đẹp sống trong rừng sâu cùng với bảy chú lùn. Công việc hàng ngày của các chú lùn là khai thác quặng. Tuy nhiên có một điều không phải ai cũng biết là làm thế nào mà các chú lùn có thể khai thác mỏ với thân hình nhỏ bé của mình? Thật thú vị là ngay từ thời ấy, các chú lùn đã sử dụng máy móc trong công việc của mình!.
Khu đất mà các chú lùn khai thác quặng có dạng hình chữ nhật được chia thành hàng và cột tạo thành lưới ô vuông. Khu đất chỉ có hai loại quặng có giá trị là vàng và bạc. Trữ lượng vàng ở ô - hàng , cột có giá trị (qui thành USD) là còn trữ lượng bạc cũng ở ô này có giá trị (qui thành USD) là . Xưởng luyện quặng vàng ở phía tây khu đất (bên trái) và Xưởng luyện quặng bạc ở phía bắc khu đất (bên trên).
Có hai loại băng chuyền vận chuyển quặng. Các băng chuyền vận chuyển quặng vàng chạy từ đông sang tây (phải sang trái) các ô mà băng chuyền này chạy qua đều khai thác vàng. Băng chuyền vận chuyển vàng luôn kết thúc ở phía tây. Các băng chuyền vận chuyển quặng bạc chạy từ nam lên bắc (từ dưới lên trên) các ô mà băng chuyền này chạy qua đều khai thác bạc. Băng chuyền sản xuất bạc luôn kết thúc ở phía bắc. Ô không có băng chuyền đi qua thì không khai thác gì cả.
Hãy tính xem các chú lùn có thể thu được nhiều nhất bao nhiêu USD từ khu đất trên.
Dữ liệu:
Dòng đầu tiên ghi hai số nguyên dương ;
dòng tiếp theo, dòng thứ ghi số ;
dòng cuối cùng, dòng thứ ghi số .
Các giá trị quặng là các số nguyên nằm trong phạm vi từ đến .
Kết quả:
Ghi ra một số nguyên duy nhất là lượng USD lớn nhất thu được.
