g6-08069. 牧场买草 · 林老师的题库

题目描述

奶牛场的草料快吃完了，饲养员要去饲料店进货。店里有 $n$ 种草料包，第 $i$ 种每包重 $p_{i}$ 千克、卖 $c_{i}$ 元，每种都能整包整包地买，不能拆开零卖，买多少包都行。饲养员至少要备够 $N$ 千克草料，多一点也没关系，但想尽量省钱。请算出最少要花多少钱。

第一行两个整数 $n, N$ 。

接下来 $n$ 行，每行两个整数 $p_{i}, c_{i}$ 。

一行一个整数，表示达到至少 $N$ 千克所需的最少总花费。

2 7
3 4
5 6

买一包 $3$ 千克和一包 $5$ 千克：共 $4 + 6 = 10$ 元，重量 $3 + 5 = 8$ 千克够了；只买 $5$ 千克那一包，重量不到 $7$ 千克。

$1 \leq n \leq 100$ ， $1 \leq N \leq 1 0^{4}$ ， $1 \leq p_{i}, c_{i} \leq 1 0^{4}$ 。数据保证一定可以凑够 $N$ 千克。