小苯有一个长度为 的序列 ，他希望你能将 划分为恰好 个非空的连续段，并将其中每一段中的数字求和，组成一个长度恰好 的新序列 。接着，最大化以下式子： 即： 中奇数位置的数字之和，加上偶数位置的数字之和 。 请你帮他算算这个最大值是多少吧。

输入描述:

本题有多组测试数据。输入的第一行包含一个正整数 ，表示数据组数。接下来包含 组数据，每组数据的格式如下：第一行两个正整数 ，表示小苯的序列 的长度，以及需要恰好划分成的连续段个数。第二行 个整数 ，表示序列 。（保证同一个测试文件的所有测试数据中， 的总和不超过 。）

输出描述:

对于每组测试数据：输出一行一个整数，表示所求式子的最大值。