J17 习题-8 收集棒棒糖

题目描述

在一条直线上均匀的分布着 $N$ 个店铺，每个店铺有 $M$ 种不同的棒棒糖出售，但佩奇决定还是电话购物。 在第 $i$ 个店铺购买 $j$ 个棒棒糖需要花费 $P_{i,j}$ 元。如果在某商店购买了少于 $Y$ 个棒棒糖，则每个棒棒糖需要额外支付 $a_i$ 元的邮费，如果购买 $Y$ 个及以上，则包邮。 在每家店只能购买一次，也就是说在每家店最多下一次订单。 现在佩奇想要 $K$ 个棒棒糖，请问最小花费是多少（总花费=总邮费+总购买费）。 请不要购买超过 $K$ 个糖，数据保证一定能够购买 $K$ 个糖。

输入格式

第一行 $4$ 个整数，$N,M,K,Y$ ； 第二行 $N$ 个整数，第 $i$ 个数表示 $a_i$ ； 接下来 $N$ 行，每行 $M$ 个数，表示 $P_{i,j}$。

输出格式

一个非负整数，表示题目描述中的最小花费。

样例输入

5 8 10 3
10 20 100 5 1
1 3 5 7 9 11 13 15
2 4 6 8 10 12 14 16
1 2 3 4 5 6 7 8
1 3 6 10 15 21 28 36
10 20 30 40 50 60 70 80

样例输出

12

样例分析

在第一家买 $3$ 个，然后在第三家店买 $7$ 个，总价为 $7+5=12$，（因为都是 $3$ 把以上，所以不用邮费）。

数据范围

$100\%$ 的数据：$1 \leq N,M,K \leq 500; K \leq Min(500,N*M; Y \leq K ; a_i \leq 100; P_{i,j} \leq 10,000,000 ; P_{i,j-1} \leq P_{i,j}$。