DSES打算出门旅行，他想好了n个绝世好去处。

每个地方都有对应的好玩度，DSES当然想每个都去一遍。但是，DSES毕竟也不是什么有钱人，当然不可能每个都去一遍。同时，每个地方还都有讨厌度，，一旦他去的那些地方的讨厌度总和大于k，那么DSES将会很失落。因为他的数学并不是很好，所以，他找到了精通编程的你，想请你帮他算算，在金钱和讨厌度的双重限制下，他最多能获得多少好玩度？（其中的每一个数均为整数）

输入格式：

第一行，输入n，q，k表示有n个地方、他有q块钱、他的讨厌度上限为k； 接下来，第2到n+1行，每行三个数字，分别表示好玩度、价格、讨厌度。

输出格式：

仅一行，输出最多可获得的好玩度。

样例 1 输入： 3 10 8 5 4 3 7 5 4 3 3 2 输出：12

样例 2 输入： 2 5 5 10 6 1 9 4 3 输出：9

样例 3 输入： 4 15 10 6 5 2 8 6 3 4 3 4 9 7 5 输出：23

样例 4 输入： 1 3 3 100 4 1 输出：0

样例 5 输入： 5 20 12 12 8 5 15 9 6 7 4 2 11 7 4 5 3 1 输出：33

样例 6 输入： 3 8 4 10 5 3 11 5 3 2 2 2 输出：11

样例 7 输入： 4 10 20 5 2 5 6 3 6 7 4 7 8 5 8 输出：18

样例 8 输入： 2 10 2 20 5 3 18 6 2 输出：18

样例 9 输入： 6 25 18 9 6 4 13 8 5 7 5 3 11 7 4 15 9 6 4 2 1 输出：44

样例 10 输入： 3 0 10 10 1 1 20 2 2 30 3 3 输出：0

@ @

DSES 的数学题

题目背景

DSES正在做数学题。 他正在对一道题目发愁：如图，建立直角坐标系$xOy$，现有三个点$A(x1,y1)、B(x2,y2)、C(x3,y3)$,按顺序依次手尾相接得到$△ABC$，试求出$S△ABC=？$ 现在，DSES给你三个点的坐标，请你帮他求出各个$S△ABC$。

输入 x1,y1,x2,y2,x3,y3,输出S;

数据范围：

1 ≤ x1,y1 ≤ x2,y2 ≤ x3,y3 ≤ 200

输出要求

仅单独输出一行，该行只有一个整数，为$S△ABC$，无其他多余文字、符号。

样例 1 输入：1 1 1 3 4 1 输出：3

样例 2 输入：2 2 2 6 7 2 输出：10

样例 3 输入：1 2 4 2 4 6 输出：6

样例 4 输入：3 1 6 1 6 7 输出：9

样例 5 输入：2 3 5 3 5 7 输出：6

样例 6 输入：1 1 5 1 3 6 输出：10

样例 7 输入：4 2 9 2 6 8 输出：15

样例 8 输入：3 3 8 3 6 9 输出：15

样例 9 输入：2 1 7 1 4 7 输出：15

样例 10 输入：4 4 9 4 6 10 输出：15

边界测试（三点共线） 输入：1 1 2 2 5 5 输出：0

建议把上次大学城集训叫“图形”的那道题放进题库

@ @ DSES 的物资采购规划 题目背景 DSES 在仓储管理中心工作，每周都要完成物资采购的规划工作。仓库的物资货架是一条直线排布的，货架上从左到右依次摆放着不同品类的物资，每一类物资如果进行批量采购，都可以获得一笔对应的收益数值。 仓储中心出台了严格的采购限制条例，为了避免单次采购占用过多仓储空间、造成货物堆积混乱，条例明确规定：不能同时采购两个位置相邻的物资。也就是说，如果 DSES 决定采购货架上第 i 个位置的物资，那么它左边 i-1 号位、右边 i+1 号位的物资都不能纳入本次采购清单。 所有物资对应的采购收益都是正整数，没有收益为零或者亏损的物资。采购没有总件数限制，DSES 可以选择只采购一件，也可以挑选多件满足规则的物资，最终目标是让本次采购所有选中物资的收益相加总和达到最大值。现在需要编写程序，根据货架物资的数量与每件物资的收益，计算出 DSES 能够拿到的最大总收益。

输入说明 第一行输入一个正整数 n，代表货架上物资的总件数，物资按照从左至右顺序编号 1~n； 第二行输入 n 个以空格隔开的正整数，依次对应第 1 件到第 n 件物资各自的采购收益。

数据范围： 1 ≤ n ≤ 2000，单件物资收益不超过 10000。

输出要求 仅单独输出一行，该行只有一个整数，为 DSES 能获取的最大采购总收益，无其他多余文字、符号。

样例输入 1 6 2 7 9 3 1 4

样例输出 1 15

样例输入 2 1 36

样例输出 2 36

样例输入 3 3 8 2 6

样例输出 3 14

样例输入 4 5 5 1 2 7 3

样例输出 4 12

太好了

感谢PPCQ,FISH

谢谢PPCQ

题目