この問題はサンプルです
注意
Sample 0 の注意事項を先にお読みください。
問題文
N 個の小パスタが繋がってできた大パスタがあります.
左から i(1≤i≤N) 番目の小パスタの長さは Li です.
この大パスタを何回か折って,いくつかの中パスタ (小パスタがいくつか繋がったもの) に再び分割しようとしています.
ただし,見栄えのために,すべての中パスタの長さが等しくなるようにする必要があります.
このとき最大でいくつの中パスタへ分割することができますか?
求めてください.
大パスタは,それを構成する小パスタ同士の繋ぎ目でのみ折ることができます.
制約
- 1≤Φ≤105
- 1≤N
- ∑ϕΦϕ(N)≤105
- 1≤Li≤100(1≤i≤N)
入力
各テストケースの入力は,それぞれ以下の形式で与えられる:
出力
答えを出力せよ.
サンプル
入力例1
2
8
1 2 3 2 4 4 2 6
5
1 2 3 4 5
- 1+2+3=2+4=4+2=6 であるので,長さ 6 の中パスタ 4 つに分割することができます.(他に,たとえば長さ 8 の中パスタ 3 つに分割することもできますが,4 が最大です.)
- 長さが ∑L の中パスタ 1 つに分割することができます.