rt

学习小组

题目描述

共有 $n$ 个学生，$m$ 个学习小组，每个学生只愿意参加其中的一些学习小组，且一个学生最多参加 $k$ 个学习小组。每个学生参加学习小组财务处都收一定的手续费，不同的学习小组有不同的手续费。若有 $a$ 个学生参加第 $i$ 个学习小组，财务处支付奖励 $C_i \times a^2$ 元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱。

输入格式

输入有若干行，第一行有三个用空格隔开的正整数 $n,m,k$。

接下来的一行有 $m$ 个正整数，表示每个 $C_i$。

第三行有 $m$ 个正整数，表示参加每个学习小组需要交的手续费 $F_i$。

再接下来有一个 $n$ 行 $m$ 列的矩阵，表若第 $i$ 行 $j$ 列的数字是 $1$，则表示第 $i$ 个学生愿意参加第 $j$ 个学习小组，若为 $0$，则为不愿意。

输出格式

输出只有一个整数，为最小的支出。

样例 #1

样例输入 #1

3 3 1
1 2 3
3 2 1
111
111
111

样例输出 #1

-2

提示

对于 $100\%$ 的数据，$0＜n\le 100，0＜m≤90，0＜k\le m，0＜C_i\le 10，0＜F_i\le 100。$

# 学习小组

## 题目描述

共有 $n$ 个学生，$m$ 个学习小组，每个学生只愿意参加其中的一些学习小组，且一个学生最多参加 $k$ 个学习小组。每个学生参加学习小组财务处都收一定的手续费，不同的学习小组有不同的手续费。若有 $a$ 个学生参加第 $i$ 个学习小组，财务处支付奖励 $C_i \times a^2$ 元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱。

## 输入格式

输入有若干行，第一行有三个用空格隔开的正整数 $n,m,k$。接下来的一行有 $m$ 个正整数，表示每个 $C_i$。第三行有 $m$ 个正整数，表示参加每个学习小组需要交的手续费 $F_i$。再接下来有一个 $n$ 行 $m$ 列的矩阵，表若第 $i$ 行 $j$ 列的数字是 $1$，则表示第 $i$ 个学生愿意参加第 $j$ 个学习小组，若为 $0$，则为不愿意。

## 输出格式

输出只有一个整数，为最小的支出。

## 样例 #1

### 样例输入 #1

3 3 1 1 2 3 3 2 1 111 111 111

### 样例输出 #1

-2

## 提示

对于 $100\%$ 的数据，$0＜n\le 100，0＜m≤90，0＜k\le m，0＜C_i\le 10，0＜F_i\le 100。$