蜗蜗准备制作一些菜肴，共有 道菜可以选择，每道菜至多制作一次。
制作第 道菜时，可以选择消耗 范围内任意实数重量的香料，并获得固定的价值 。不制作这道菜则不会消耗香料，也不会获得价值。
蜗蜗希望香料的总消耗恰好为 。请你求出能够获得的最大总价值；如果无法恰好消耗 重量的香料，则输出 。
第一行包含两个整数 和 ，分别表示需要消耗的香料总重量和可以选择的菜肴数量。
接下来 行，第 行包含三个整数 ，分别表示制作第 道菜时可以消耗的香料重量下限、上限，以及获得的价值。
输出一行一个整数，表示能够获得的最大总价值。如果无法恰好消耗 重量的香料，输出 。
5 2
2 3 4
2 4 7
11
选择制作两道菜，第一道菜消耗 重量的香料，第二道菜消耗 重量的香料。
总消耗为 ，恰好等于 ，总价值为 。
对于 100% 的数据，保证 ，，，。
所有输入量均为整数，但制作菜肴时选择的香料重量可以是实数。