ABC-063-C Bugged

■■■問題■■■

あなたはコンピュータで試験を受けています。
試験はN問の問題からなり、i問目の問題の配点はsiです。

それぞれの問題に対するあなたの解答は「正解」または「不正解」のいずれかとして判定され、
正解した問題の配点の合計があなたの成績となります。

あなたが解答を終えると、
解答がその場で採点されて成績が表示される ・・・ はずでした。

ところが、試験システムに欠陥があり、
成績が10の倍数の場合は、画面上で成績が0と表示されてしまいます。
それ以外の場合は、画面に正しい成績が表示されます。

この状況で、成績として画面に表示されうる最大の値はいくつでしょうか？

■■■入力■■■

N
s1
s2
・
・
・
sN

●入力値はすべて整数である
●1 <= N  <= 100
●1 <= si <= 100

■■■出力■■■

成績として画面に表示されうる最大の値を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("5");
            WillReturn.Add("10");
            WillReturn.Add("15");
            //25
            //10点の問題と15点の問題に正解し、
            // 5点の問題には正解しないことで成績が25となり、
            //この成績は画面に正しく表示されます。
            //
            // 5点の問題にも正解すると成績が30となりますが、
            //この成績は画面上では0と表示されてしまいます。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("15");
            //35
            //すべての問題に正解すると成績が35となり、
            //この成績は画面に正しく表示されます。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("10");
            WillReturn.Add("20");
            WillReturn.Add("30");
            //0
            //どのような解答状況でも成績は10の倍数となり、
            //画面上では0と表示されてしまいます。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList.Skip(1).Select(X => int.Parse(X)).ToArray();

        //可能な和のSet
        var SumSet = new HashSet<int>();
        SumSet.Add(0);

        foreach (int EachInt in AArr) {
            foreach (int EachSum in SumSet.ToArray()) {
                int NewSum = EachSum + EachInt;
                SumSet.Add(NewSum);
            }
        }

        int Answer = 0;
        foreach (int EachSum in SumSet) {
            if (EachSum % 10 == 0) continue;

            if (Answer < EachSum) {
                Answer = EachSum;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

到達可能な得点を動的計画法で列挙してます。