Cannot parse: (0 , import_utils.normalizeSubtasks) is not a function or its return value is not iterable

Background

Special for beginners, ^_^

Description

小 A 有一天扶老奶奶过马路，老奶奶为了报答小 A ，给了他一条数轴和 n 条金条奖励。

但是这 n 条金条黏在了一块积木板上，小 A 一旦把它们拿去换钱，他们就会飞回积木板上。

小 A 愁昏了头，但是他细心的发现，每根金条上写着四个数字和数字的解释，并且在数轴上刻画着几行字。

这四个数字分别是:

• Si: 该金条在数轴上的起点
• Wi: 该金条的长度
• Vi: 该金条所能获得的价钱
• Ci​: 把该金条放到数轴对应位置所需支付的价钱。

数轴上的文字是:

• 假若你将一根金条放到数轴对应位置上，你可获得该金条对应的价钱，但是你必须刚好铺满 [0,L] 的这块区域。
• 铺上去的金条必须首尾相连，不可以重叠，也不可以空缺，否则你将一无所获。

小 A 抠抠搜搜一共就只有 B 元钱，他想请你帮帮他，怎样安排他才能拿到最多的金钱？

注意:你必须要刚好铺满 0~L 这块区域才可以获得价值

Format

Input

第一行输入三个整数L,n,B(1≤L≤10³,1≤n≤10⁴,0≤B≤10³)

随后 n 行，每行输入四个整数 Si​(0≤Si​≤L−Wi​), Wi(1≤Wi≤L), Vi(1≤Vi​≤10⁶), Ci(1≤Ci​≤10³)，代表每根金条的信息。

注意只有一次完整地机会

Output

输出一个数字，代表小 A 能够获得最大的价值，如果一无所获，那么请输出-1。

Samples

5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2

17

Limitation

1s, 1024KiB for each test case.