using System;

using System.Collections.Generic;

using System.Linq;

class element : IComparable

    {

        public int number;

        public int weight;

        public element(int number, int weight)

        {

            this.number = number;

            this.weight = weight;

        }

​

        public int CompareTo(object el)

        {

            element myel = (element)el;

            return this.number.CompareTo(myel.number);

        }

    }

public class Program

{

    public static void Main()

    {

        //int[,] inputSequence = { { 1, 10 }, { 2, 20 }, { 3, 30 }, { 4, 40}, { 1, 15}, { 2, 15}, { 3, 15}, { 4, 50} };

            List<element> inputSequence = new List<element>

            {

                new element(1,10),

                new element(2,20) , 

                new element(3,30) , 

                new element(4,40) , 

                new element(1,15) , 

                new element(2,15) , 

                new element(3,15) , 

                new element(4,50)

​

            };

​

            //generating subSequence 

​

            int combCount = (int)Math.Pow(2, inputSequence.Count) - 1;

            List<List<element>> SubSequence = new List<List<element>>();

            for (int i = 1; i < combCount + 1; i++)

            {

                SubSequence.Add(new List<element>());

                for (int j = 0; j < inputSequence.Count; j++)

                {

                    if ((i >> j) % 2 != 0)

                        SubSequence.Last().Add(inputSequence[j]);

                }

            }

​

​

            //delete not increasing subsequences

            for(int i =0; i<SubSequence.Count; i++)

            {

                int subCount = SubSequence[i].Count;

                int j = 0;

                int removed = 0;

                while (removed ==0&&j<subCount-1)

                {

                    if(SubSequence[i][j].CompareTo(SubSequence[i][j+1]) >= 0)

                    {

                        SubSequence.RemoveAt(i);

                        removed = 1;

                        i--;

                    }

                    j++;

                }

            }

​

            //get max weight

            int maxWeight = 0;

            for (int i = 0; i < SubSequence.Count; i++)

            {

                int weight = 0;

                SubSequence[i].ForEach(sub => weight += sub.weight);

                if (weight > maxWeight) maxWeight = weight;

​

            }

            //Console.WriteLine($"max weight is: {maxWeight}");

            Console.WriteLine("max weight is: " + maxWeight);

​

    }

}